Induced subgraphs and well-quasi-ordering

We study classes of finite, simple, undirected graphs that are (1) lower ideals (or hereditary) in the partial order of graphs by the induced subgraph relation ≤_i, and (2) well-quasi-ordered (WQO) by this relation. The main result shows that the class of cographs (P₄-free graphs) is WQO by ≤_i, and that this is the unique maximal lower ideal with one forbidden subgraph that is WQO. This is a consequence of the famous Kruskal theorem. Modifying our idea we can prove that P₄-reducible graphs build a WQO class. Other examples of lower ideals WQO by ≤_i are also given.     

Two forbidden induced subgraphs and well-quasi-ordering

It is known that a class of graphs defined by a single forbidden induced subgraph G is well-quasi-ordered by the induced subgraph relation if and only if G is an induced subgraph of P₄. However, very little is known about well-quasi-ordered classes of graphs defined by more than one forbidden induced subgraph. We conjecture that for any natural number k, there are finitely many minimal classes of graphs defined by k forbidden induced subgraphs which are not well-quasi-ordered by the induced subgraph relation and prove the conjecture for k=2. We explicitly reveal many of the minimal classes defined by two forbidden induced subgraphs which are not well-quasi-ordered and many of those which are well-quasi-ordered by the induced subgraph relation.     

On well-quasi-ordering finite structures with labels

A quasi-ordered setA (i.e. one equipped with a reflexive and transitive relation ) is said to be well-quasi-ordered (wqo) if for every infinite sequencea ₁,a ₂, ... of elements ofA there are indicesi, j such thati < j anda _i a _j.Various natural wqo setsQ admit labelling by another wqoA yielding another quasi-ordered setQ(A), which may or may not be wqo. A suitable concept covering this phenomenon is the notion of aQO-category. We have two conjectures aboutQO-categories in the effect that labellingQO-categories by a wqo set can always be reduced to labelling by ordinals. We prove these conjectures for a broad class ofQO-categories and for generalQO-categories we prove weaker forms of these conjectures.     

Largest Non-Unique Subgraphs

The reduction number r(G) of a graph G is the maximum integer m≤|E(G)| such that the graphs G−E, E⊆E(G),|E|≤m, are mutually non-isomorphic, i.e., each graph is unique as a subgraph of G. We prove that and show by probabilistic methods that r(G) can come close to this bound for large orders. By direct construction, we exhibit graphs with large reduction number, although somewhat smaller than the upper bound. We also discuss similarities to a parameter introduced by Erdős and Rényi capturing the degree of asymmetry of a graph, and we consider graphs with few circuits in some detail. Supported by a grant from the Danish Natural Science Research Council.     

Bipartite Subgraphs and Quasi-Randomness

We say that a family of graphs is p-quasi-random, 0<p<1, if it shares typical properties of the random graph G(n,p); for a definition, see below. We denote by the class of all graphs H for which and the number of not necessarily induced labeled copies of H in G_n is at most (1+o(1))p^e(H)n^v(H) imply that is p-quasi-random. In this note, we show that all complete bipartite graphs K_a,b, a,b2, belong to for all 0<p<1.Acknowledgments We would like to thank Andrew Thomason for fruitful discussions and Yoshi Kohayakawa for organizing Extended Workshop on Combinatorics in eq5 Paulo, Ubatuba, and Rio de Janeiro, where a part of this work was done. We also thank the referees for their careful work.The first author was partially supported by NSF grant INT-0072064The second author was partially supported by NSF grants DMS-9970622, DMS-0301228 and INT-0072064Final version received: October 24, 2003     

Strong immersion is a well-quasi-ordering for semicomplete digraphs

We prove that the strong immersion order is a well-quasi-ordering on the class of semicomplete digraphs, thereby strengthening a result of Chudnovsky and Seymour (2011, J. Comb. Theory, Series B, 101, 47–53) that this holds for the class of tournaments.     

Counting Unbranched Subgraphs

Given an arbitrary finite graph, the polynomial associates a weight zcardF to each unbranched subgraph F of length cardF. We show that all the zeros of Q have negative real part.     

γ-可图序列与γ-完全子图

一个r-图是一个无环的无向图,其中任何两个顶点之间至多被r条边连接.一个m+1个顶点的r-完全图,记为K_(m+1)^((r)),是一个m+1个顶点的r-图,其中任何两个顶点之间恰好被r条边连接.一个非增的非负整数序列π=(d_1,d_2,…,d_n)称为是r-可图的如果它是某个n个顶点的r-图的度序列.一个r-可图序列π称为是蕴含(强迫)K_(m+1)((r)),是一个m+1个顶点的r-图,其中任何两个顶点之间恰好被r条边连接.一个非增的非负整数序列π=(d_1,d_2,…,d_n)称为是r-可图的如果它是某个n个顶点的r-图的度序列.一个r-可图序列π称为是蕴含(强迫)K_(m+1)^((r))可图的如果π有一个实现包含K_(m+1)((r))可图的如果π有一个实现包含K_(m+1)^((r))作为子图(π的每一个实现包含K_(m+1)((r))作为子图(π的每一个实现包含K_(m+1)^((r))作为子图).设σ(K_(m+1)((r))作为子图).设σ(K_(m+1)^((r)),n)(τ(K_(m+1)((r)),n)(τ(K_(m+1)^((r)),n))表示最小的偶整数t,使得每一个r-可图序列π=(d_1,d_2,…,d_n)具有∑_(i=1)((r)),n))表示最小的偶整数t,使得每一个r-可图序列π=(d_1,d_2,…,d_n)具有∑_(i=1)ⁿ d_i≥t是蕴含(强迫)K_(m+1)n d_i≥t是蕴含(强迫)K_(m+1)^((r))-可图的.易见,σ(K_(m+1)((r))-可图的.易见,σ(K_(m+1)^((r)),n)是Erds等人的一个猜想从1-图到r-图的扩充且τ(K_(m+1)((r)),n)是Erds等人的一个猜想从1-图到r-图的扩充且τ(K_(m+1)^((r)),n)是经典Turan定理从1-图到r-图的扩充.本文给出了蕴含K_(m+1)((r)),n)是经典Turan定理从1-图到r-图的扩充.本文给出了蕴含K_(m+1)^((r))的r-可图序列的两个简单充分条件.此两个条件包含了Yin和Li在[Discrete Math.,2005,301:218-227]中的两个主要结果和当n≥max{m((r))的r-可图序列的两个简单充分条件.此两个条件包含了Yin和Li在[Discrete Math.,2005,301:218-227]中的两个主要结果和当n≥max{m²+3m+1-[(m2+3m+1-[(m²+m)/r],2m+1+[m/r]]}时,σ(K_(m+1)2+m)/r],2m+1+[m/r]]}时,σ(K_(m+1)^((r)),n)之值.此外,我们还确定了当n≥m+1时,τ(K_(m+1)((r)),n)之值.此外,我们还确定了当n≥m+1时,τ(K_(m+1)^((r)),n)之值.     

PM-compact Graphs and Vertex-deleted Subgraphs

Acta Mathematicae Applicatae Sinica, English Series - The perfect matching polytope of a graph G is the convex hull of the incidence vectors of all perfect matchings of G. A graph G is PM-compact...     

Factors and Connected Induced Subgraphs

 Let G be a connected graph without loops and without multiple edges, and let p be an integer such that 0 < p<|V(G)|. Let f be an integer-valued function on V(G) such that 2≤f(x)≤ deg _G (x) for all x∈V(G). We show that if every connected induced subgraph of order p of G has an f-factor, then G has an f-factor, unless ∑ _{x ∈ V ( G )} f(x) is odd. Received: June 29, 1998?Final version received: July 30, 1999     

The theory of well-quasi-ordering: A frequently discovered concept

Results from the rich and well-developed theory of well-quasi-ordering have often been rediscovered and republished. The purpose of this paper is to describe this intriguing subject. To illustrate the theory, here are two definitions and an elementary result. A partially ordered set is called well-partially-ordered if every subset has at least one, but only a finite number, of minimal elements. For sequences s and t, we define s ? t if some subsequence of t majorizes s term by term. Then the space of all finite sequences over a well-partially-ordered set is itself well-partially-ordered.     

Highly Symmetric Subgraphs of Hypercubes

Two questions are considered, namely (i) How many colors are needed for a coloring of the n-cube without monochromatic quadrangles or hexagons? We show that four colors suffice and thereby settle a problem of Erdös. (ii) Which vertex-transitive induced subgraphs does a hypercube have? An interesting graph has come up in this context: If we delete a Hamming code from the 7-cube, the resulting graph is 6-regular, vertex-transitive and its edges can be two-colored such that the two monochromatic subgraphs are isomorphic, cubic, edge-transitive, nonvertex-transitive graphs of girth 10.     

On Subgraphs in Distance-Regular Graphs

Terwilliger [15] has given the diameter bound d (s – 1)(k – 1) + 1 for distance-regular graphs with girth 2s and valency k. We show that the only distance-regular graphs with even girth which reach this bound are the hypercubes and the doubled Odd graphs. Also we improve this bound for bipartite distance-regular graphs. Weichsel [17] conjectures that the only distance-regular subgraphs of a hypercube are the even polygons, the hypercubes and the doubled Odd graphs and proves this in the case of girth 4. We show that the only distance-regular subgraphs of a hypercube with girth 6 are the doubled Odd graphs. If the girth is equal to 8, then its valency is at most 12.     

Subgraphs of Random Match-Graphs

 A simple graph (match-graph) generated by two-cycles of a general model of a random digraph is considered. Based on relations between a special case of such a graph and a classical model of a random graph, some results about the existence and the number of subgraphs of a given type in a random match-graph are presented. Received: December 8, 1997 Final version received: September 16, 1999     

Subgraphs of colour-critical graphs

Some problems and results on the distribution of subgraphs in colour-critical graphs are discussed. In section 3 arbitrarily largek-critical graphs withn vertices are constructed such that, in order to reduce the chromatic number tok−2, at leastc _k n ² edges must be removed. In section 4 it is proved that a 4-critical graph withn vertices contains at mostn triangles. Further it is proved that ak-critical graph which is not a complete graph contains a (k−1)-critical graph which is not a complete graph.     

Subgraphs smaller than the girth

For graphs A, B, let () denote the number of subsets of nodes of A for which the induced subgraph is B. If G and H both have girth > k, and if () = () for every k-node tree T, then for every k-node forest F, () = (). Say the spread of a tree is the number of nodes in a longest path. If G is regular of degree d, on n nodes, with girth > k, and if F is a forest of total spread ≤k, then the value of () depends only on n and d.     

Graphs without K4 and well-quasi-ordering

It is proved that given an infinite sequence G₁, G₂, G₃,…, of series-parallel graphs there are indices i < j such that G_j contains an induced subgraph contractable onto G_i. An example is given showing that for planar graphs the preceding theorem fails.