LS sets as cohesive subsets of graphs and hypergraphs

For social scientists, a ‘clique’ has long been seen as a subset of a population whose members are more tightly linked to other members of the subset than they are to non-members. Similar ideas have arisen in clustering theory. Most approaches to the problem of defining such subsets have concentrated either on maximizing the number of intra-subset ties or minimizing the number of inter-subset ties. LS sets in graphs or hypergraphs provide a way of addressing simultaneously both intra-subset ties and inter-subset ties. A new characterization of LS sets is given and used to derive simple proofs of several important results on LS sets.     

Centered graphs and the structure of ego networks

A way of comparing ego networks through examining patterns among their ties is introduced. It is derived from graph-theoretic ideas about centered graphs. An illustration using data from a computer conference is provided.     

Outerplanar and Planar Oriented Cliques

The clique number of an undirected graph G is the maximum order of a complete subgraph of G and is a well‐known lower bound for the chromatic number of G. Every proper k‐coloring of G may be viewed as a homomorphism (an edge‐preserving vertex mapping) of G to the complete graph of order k. By considering homomorphisms of oriented graphs (digraphs without cycles of length at most 2), we get a natural notion of (oriented) colorings and oriented chromatic number of oriented graphs. An oriented clique is then an oriented graph whose number of vertices and oriented chromatic number coincide. However, the structure of oriented cliques is much less understood than in the undirected case. In this article, we study the structure of outerplanar and planar oriented cliques. We first provide a list of 11 graphs and prove that an outerplanar graph can be oriented as an oriented clique if and only if it contains one of these graphs as a spanning subgraph. Klostermeyer and MacGillivray conjectured that the order of a planar oriented clique is at most 15, which was later proved by Sen. We show that any planar oriented clique on 15 vertices must contain a particular oriented graph as a spanning subgraph, thus reproving the above conjecture. We also provide tight upper bounds for the order of planar oriented cliques of girth k for all .     

Local Clique Covering of Claw‐Free Graphs

A clique covering of a simple graph G is a collection of cliques of G covering all the edges of G such that each vertex is contained in at most k cliques. The smallest k for which G admits a clique covering is called the local clique cover number of G and is denoted by lcc(G). Local clique cover number can be viewed as the local counterpart of the clique cover number that is equal to the minimum total number of cliques covering all edges. In this article, several aspects of the local clique covering problem are studied and its relationships to other well‐known problems are discussed. In particular, it is proved that the local clique cover number of every claw‐free graph is at most , where Δ is the maximum degree of the graph and c is a constant. It is also shown that the bound is tight, up to a constant factor. Moreover, regarding a conjecture by Chen et al. (Clique covering the edges of a locally cobipartite graph, Discrete Math 219(1–3)(2000), 17–26), we prove that the clique cover number of every connected claw‐free graph on n vertices with the minimum degree δ, is at most , where c is a constant.     

Unique Colorability and Clique Minors

For a graph G, let denote the largest k such that G has k pairwise disjoint pairwise adjacent connected nonempty subgraphs, and let denote the largest k such that G has k pairwise disjoint pairwise adjacent connected subgraphs of size 1 or 2. Hadwiger 's conjecture states that , where is the chromatic number of G. Seymour conjectured for all graphs without antitriangles, that is,  three pairwise nonadjacent vertices. Here we concentrate on graphs G with exactly one ‐coloring. We prove generalizations of the following statements: (i) if and G has exactly one ‐coloring then , where the proof does not use the four‐color‐theorem, and (ii) if G has no antitriangles and G has exactly one ‐coloring then .     

Cliques in dense inhomogeneous random graphs

The theory of dense graph limits comes with a natural sampling process which yields an inhomogeneous variant of the Erd?s–Rényi random graph. Here we study the clique number of these random graphs. We establish the concentration of the clique number of for each fixed n , and give examples of graphons for which exhibits wild long‐term behavior. Our main result is an asymptotic formula which gives the almost sure clique number of these random graphs. We obtain a similar result for the bipartite version of the problem. We also make an observation that might be of independent interest: Every graphon avoiding a fixed graph is countably‐partite. © The Authors Random Structures & Algorithms Published byWiley Periodicals, Inc. Random Struct. Alg., 2016 © 2017 The Authors Random Structures & Algorithms Published by Wiley Periodicals, Inc. Random Struct. Alg., 51, 275–314, 2017     

基于最优重构的病理嗓音基频检测算法研究

提出了一种基于多级小波分解重构和非线性动力学参数的病理嗓音基音频率检测算法。首先对病理嗓音进行多级小波分解及重构,然后采用最大李雅普诺夫指数和近似熵表征不同重构嗓音的规则度从而自适应地选择周期性最优的小波重构嗓音信号,以直接提取基音频率。实验结果表明。与传统的基音检测算法相比,该方法有效地避免了检测中所存在的倍频及分频误差,提高了病理嗓音检测的鲁棒性及准确度。     

Dense graphs with small clique number

We consider the structure of K_r‐free graphs with large minimum degree, and show that such graphs with minimum degree δ>(2r ? 5)n/(2r ? 3) are homomorphic to the join K_{r ? 3}∨H, where H is a triangle‐free graph. In particular this allows us to generalize results from triangle‐free graphs and show that K_r‐free graphs with such a minimum degree have chromatic number at most r +1. We also consider the minimum‐degree thresholds for related properties. Copyright © 2010 John Wiley & Sons, Ltd. 66:319‐331, 2011     

Compact topological minors in graphs

Let ε be a real number such that and t a positive integer. Let n be a sufficiently large positive integer as a function of t and ε. We show that every n‐vertex graph with at least n^1+ε edges contains a subdivision of K_t in which each edge of K_t is subdivided less than 10/ε times. This refines the main result in [A. Kostochka and Pyber, Combinatorica 8 (1988), 83–86] and resolves an open question raised there. We also pose some questions. © 2010 Wiley Periodicals, Inc. J Graph Theory 67:139‐152, 2011     

On hitting all maximum cliques with an independent set

We prove that every graph G for which has an independent set I such that ω(G?I)<ω(G). It follows that a minimum counterexample G to Reed's conjecture satisfies and hence also . This also applies to restrictions of Reed's conjecture to hereditary graph classes, and in particular generalizes and simplifies King, Reed and Vetta's proof of Reed's conjecture for line graphs. © 2010 Wiley Periodicals, Inc. J Graph Theory 66: 32–37, 2010