Minimum Degrees of Minimal Ramsey Graphs for Almost‐Cliques

For graphs F and H, we say F is Ramsey for H if every 2‐coloring of the edges of F contains a monochromatic copy of H. The graph F is Ramsey H‐minimal if F is Ramsey for H and there is no proper subgraph of F so that is Ramsey for H. Burr et al. defined to be the minimum degree of F over all Ramsey H‐minimal graphs F. Define to be a graph on vertices consisting of a complete graph on t vertices and one additional vertex of degree d. We show that for all values ; it was previously known that , so it is surprising that is much smaller. We also make some further progress on some sparser graphs. Fox and Lin observed that for all graphs H, where is the minimum degree of H; Szabó et al. investigated which graphs have this property and conjectured that all bipartite graphs H without isolated vertices satisfy . Fox et al. further conjectured that all connected triangle‐free graphs with at least two vertices satisfy this property. We show that d‐regular 3‐connected triangle‐free graphs H, with one extra technical constraint, satisfy ; the extra constraint is that H has a vertex v so that if one removes v and its neighborhood from H, the remainder is connected.     

Forbidden Pairs of Disconnected Graphs Implying Hamiltonicity

Let H be a given graph. A graph G is said to be H‐free if G contains no induced copies of H. For a class of graphs, the graph G is ‐free if G is H‐free for every . Bedrossian characterized all the pairs of connected subgraphs such that every 2‐connected ‐free graph is hamiltonian. Faudree and Gould extended Bedrossian's result by proving the necessity part of the result based on infinite families of non‐hamiltonian graphs. In this article, we characterize all pairs of (not necessarily connected) graphs such that there exists an integer n₀ such that every 2‐connected ‐free graph of order at least n₀ is hamiltonian.     

Cayley Graphs of Diameter Two from Difference Sets

Let and be the largest order of a Cayley graph and a Cayley graph based on an abelian group, respectively, of degree d and diameter k. When , it is well known that with equality if and only if the graph is a Moore graph. In the abelian case, we have . The best currently lower bound on is for all sufficiently large d. In this article, we consider the construction of large graphs of diameter 2 using generalized difference sets. We show that for sufficiently large d and if , and m is odd.     

On the Minimum Number of Spanning Trees in k‐Edge‐Connected Graphs

We show that a k‐edge‐connected graph on n vertices has at least spanning trees. This bound is tight if k is even and the extremal graph is the n‐cycle with edge multiplicities . For k odd, however, there is a lower bound , where . Specifically, and . Not surprisingly, c₃ is smaller than the corresponding number for 4‐edge‐connected graphs. Examples show that . However, we have no examples of 5‐edge‐connected graphs with fewer spanning trees than the n‐cycle with all edge multiplicities (except one) equal to 3, which is almost 6‐regular. We have no examples of 5‐regular 5‐edge‐connected graphs with fewer than spanning trees, which is more than the corresponding number for 6‐regular 6‐edge‐connected graphs. The analogous surprising phenomenon occurs for each higher odd edge connectivity and regularity.     

The Maximum Number of Complete Subgraphs of Fixed Size in a Graph with Given Maximum Degree

In this article, we make progress on a question related to one of Galvin that has attracted substantial attention recently. The question is that of determining among all graphs G with n vertices and , which has the most complete subgraphs of size t, for . The conjectured extremal graph is , where with . Gan et al. (Combin Probab Comput 24(3) (2015), 521–527) proved the conjecture when , and also reduced the general conjecture to the case . We prove the conjecture for and also establish a weaker form of the conjecture for all r.     

Amalgams and χ‐Boundedness

A class of graphs is hereditary if it is closed under isomorphism and induced subgraphs. A class of graphs is χ‐bounded if there exists a function such that for all graphs , and all induced subgraphs H of G, we have that . We prove that proper homogeneous sets, clique‐cutsets, and amalgams together preserve χ‐boundedness. More precisely, we show that if and are hereditary classes of graphs such that is χ‐bounded, and such that every graph in either belongs to or admits a proper homogeneous set, a clique‐cutset, or an amalgam, then the class is χ‐bounded. This generalizes a result of [J Combin Theory Ser B 103(5) (2013), 567–586], which states that proper homogeneous sets and clique‐cutsets together preserve χ‐boundedness, as well as a result of [European J Combin 33(4) (2012), 679–683], which states that 1‐joins preserve χ‐boundedness. The house is the complement of the four‐edge path. As an application of our result and of the decomposition theorem for “cap‐free” graphs from [J Graph Theory 30(4) (1999), 289–308], we obtain that if G is a graph that does not contain any subdivision of the house as an induced subgraph, then .     

Petersen Cores and the Oddness of Cubic Graphs

Let G be a bridgeless cubic graph. Consider a list of k 1‐factors of G. Let be the set of edges contained in precisely i members of the k 1‐factors. Let be the smallest over all lists of k 1‐factors of G. We study lists by three 1‐factors, and call with a ‐core of G. If G is not 3‐edge‐colorable, then . In Steffen (J Graph Theory 78 (2015), 195–206) it is shown that if , then is an upper bound for the girth of G. We show that bounds the oddness of G as well. We prove that . If , then every ‐core has a very specific structure. We call these cores Petersen cores. We show that for any given oddness there is a cyclically 4‐edge‐connected cubic graph G with . On the other hand, the difference between and can be arbitrarily big. This is true even if we additionally fix the oddness. Furthermore, for every integer , there exists a bridgeless cubic graph G such that .     

Expression for the Number of Spanning Trees of Line Graphs of Arbitrary Connected Graphs

For any graph G, let be the number of spanning trees of G, be the line graph of G, and for any nonnegative integer r, be the graph obtained from G by replacing each edge e by a path of length connecting the two ends of e. In this article, we obtain an expression for in terms of spanning trees of G by a combinatorial approach. This result generalizes some known results on the relation between and and gives an explicit expression if G is of order and size in which s vertices are of degree 1 and the others are of degree k. Thus we prove a conjecture on for such a graph G.     

List‐Coloring the Squares of Planar Graphs without 4‐Cycles and 5‐Cycles

Let G be a planar graph without 4‐cycles and 5‐cycles and with maximum degree . We prove that . For arbitrarily large maximum degree Δ, there exist planar graphs of girth 6 with . Thus, our bound is within 1 of being optimal. Further, our bound comes from coloring greedily in a good order, so the bound immediately extends to online list‐coloring. In addition, we prove bounds for ‐labeling. Specifically, and, more generally, , for positive integers p and q with . Again, these bounds come from a greedy coloring, so they immediately extend to the list‐coloring and online list‐coloring variants of this problem.     

Equimatchable Graphs on Surfaces

A graph G is equimatchable if each matching in G is a subset of a maximum‐size matching and it is factor critical if has a perfect matching for each vertex v of G. It is known that any 2‐connected equimatchable graph is either bipartite or factor critical. We prove that for 2‐connected factor‐critical equimatchable graph G the graph is either or for some n for any vertex v of G and any minimal matching M such that is a component of . We use this result to improve the upper bounds on the maximum number of vertices of 2‐connected equimatchable factor‐critical graphs embeddable in the orientable surface of genus g to if and to if . Moreover, for any nonnegative integer g we construct a 2‐connected equimatchable factor‐critical graph with genus g and more than vertices, which establishes that the maximum size of such graphs is . Similar bounds are obtained also for nonorientable surfaces. In the bipartite case for any nonnegative integers g, h, and k we provide a construction of arbitrarily large 2‐connected equimatchable bipartite graphs with orientable genus g, respectively nonorientable genus h, and a genus embedding with face‐width k. Finally, we prove that any d‐degenerate 2‐connected equimatchable factor‐critical graph has at most vertices, where a graph is d‐degenerate if every its induced subgraph contains a vertex of degree at most d.     

A Hypercube Variant with Small Diameter

This article introduces a new variant of hypercubes . The n‐dimensional twisted hypercube is obtained from two copies of the ‐dimensional twisted hypercube by adding a perfect matching between the vertices of these two copies of . We prove that the n‐dimensional twisted hypercube has diameter . This improves on the previous known variants of hypercube of dimension n and is optimal up to an error of order . Another type of hypercube variant that has similar structure and properties as is also discussed in the last section.     

Matching Extension Missing Vertices and Edges in Triangulations of Surfaces

Let G be a 5‐connected triangulation of a surface Σ different from the sphere, and let be the Euler characteristic of Σ. Suppose that with even and M and N are two matchings in of sizes m and n respectively such that . It is shown that if the pairwise distance between any two elements of is at least five and the face‐width of the embedding of G in Σ is at least , then there is a perfect matching M₀ in containing M such that .     

Locally Symmetric Graphs of Girth 4

We classify the family of connected, locally symmetric graphs of girth 4 (finite and infinite). They are all regular, with the exception of the complete bipartite graph . There are, up to isomorphism, exactly four such k‐regular graphs for every , one for , two for , and exactly three for every infinite cardinal k. In the last paragraph, we consider locally symmetric graphs of girth >4.     

On the Probability that a Random Subgraph Contains a Circuit

Let and . We show that, if G is a sufficiently large simple graph of average degree at least μ, and H is a random spanning subgraph of G formed by including each edge independently with probability , then H contains a cycle with probability at least .     

Even Embeddings of the Complete Graphs and Their Cycle Parities

The complete graph on n vertices can be quadrangularly embedded on an orientable (resp. nonorientable) closed surface F² with Euler characteristic if and only if (resp. and ). In this article, we shall show that if quadrangulates a closed surface F², then has a quadrangular embedding on F² so that the length of each closed walk in the embedding has the parity specified by any given homomorphism , called the cycle parity.     

A Note on the Order of Iterated Line Digraphs

Given a digraph G, we propose a new method to find the recurrence equation for the number of vertices of the k‐iterated line digraph , for , where . We obtain this result by using the minimal polynomial of a quotient digraph of G.     

Subcubic Edge‐Chromatic Critical Graphs Have Many Edges

We consider graphs G with such that and for every edge e, so‐called critical graphs. Jakobsen noted that the Petersen graph with a vertex deleted, , is such a graph and has average degree only . He showed that every critical graph has average degree at least , and asked if is the only graph where equality holds. A result of Cariolaro and Cariolaro shows that this is true. We strengthen this average degree bound further. Our main result is that if G is a subcubic critical graph other than , then G has average degree at least . This bound is best possible, as shown by the Hajós join of two copies of .     

(1, k)‐Coloring of Graphs with Girth at Least Five on a Surface

A graph is ‐colorable if its vertex set can be partitioned into r sets so that the maximum degree of the graph induced by is at most for each . For a given pair , the question of determining the minimum such that planar graphs with girth at least g are ‐colorable has attracted much interest. The finiteness of was known for all cases except when . Montassier and Ochem explicitly asked if d₂(5, 1) is finite. We answer this question in the affirmative with ; namely, we prove that all planar graphs with girth at least five are (1, 10)‐colorable. Moreover, our proof extends to the statement that for any surface S of Euler genus γ, there exists a where graphs with girth at least five that are embeddable on S are (1, K)‐colorable. On the other hand, there is no finite k where planar graphs (and thus embeddable on any surface) with girth at least five are (0, k)‐colorable.     

Stability of Hereditary Graph Classes Under Closure Operations

If is a subclass of the class of claw‐free graphs, then is said to be stable if, for any , the local completion of G at any vertex is also in . If is a closure operation that turns a claw‐free graph into a line graph by a series of local completions and is stable, then for any . In this article, we study stability of hereditary classes of claw‐free graphs defined in terms of a family of connected closed forbidden subgraphs. We characterize line graph preimages of graphs in families that yield stable classes, we identify minimal families that yield stable classes in the finite case, and we also give a general background for techniques for handling unstable classes by proving that their closure may be included into another (possibly stable) class.     

Saturation Numbers in Tripartite Graphs

Given graphs H and F, a subgraph is an F‐saturated subgraph of H if , but for all . The saturation number of F in H, denoted , is the minimum number of edges in an F‐saturated subgraph of H. In this article, we study saturation numbers of tripartite graphs in tripartite graphs. For and n₁, n₂, and n₃ sufficiently large, we determine and exactly and within an additive constant. We also include general constructions of ‐saturated subgraphs of with few edges for .