Sufficient conditions for the existence of a path‐factor which are related to odd components

In this article, we are concerned with sufficient conditions for the existence of a ‐factor. We prove that for , there exists such that if a graph G satisfies for all , then G has a ‐factor, where is the number of components C of with . On the other hand, we construct infinitely many graphs G having no ‐factor such that for all .     

Smallest domination number and largest independence number of graphs and forests with given degree sequence

For a sequence d of nonnegative integers, let and be the sets of all graphs and forests with degree sequence d, respectively. Let , , , and where is the domination number and is the independence number of a graph G. Adapting results of Havel and Hakimi, Rao showed in 1979 that can be determined in polynomial time. We establish the existence of realizations with , and with and that have strong structural properties. This leads to an efficient algorithm to determine for every given degree sequence d with bounded entries as well as closed formulas for and .     

A simple formula for the number of spanning trees of line graphs

Suppose is a loopless graph and is the graph obtained from G by subdividing each of its edges k () times. Let be the set of all spanning trees of G, be the line graph of the graph and be the number of spanning trees of . By using techniques from electrical networks, we first obtain the following simple formula: Then we find it is in fact equivalent to a complicated formula obtained recently using combinatorial techniques in [F. M. Dong and W. G. Yan, Expression for the number of spanning trees of line graphs of arbitrary connected graphs, J. Graph Theory. 85 (2017) 74–93].     

Nonseparating Cycles Avoiding Specific Vertices

Thomassen proved that every ‐connected graph G contains an induced cycle C such that is k‐connected, establishing a conjecture of Lovász. In general, one could ask the following question: For any positive integers , does there exist a smallest positive integer such that for any ‐connected graph G, any with , and any , there is an induced cycle C in such that and is l‐connected? The case when is a well‐known conjecture of Lovász that is still open for . In this article, we prove and . We also consider a weaker version: For any positive integers , is there a smallest positive integer such that for every ‐connected graph G and any with , there is an induced cycle C in such that is l‐connected? The case when was studied by Thomassen. We prove and .     

A relaxation of the strong Bordeaux Conjecture

Let be k nonnegative integers. A graph G is ‐colorable if the vertex set can be partitioned into k sets , such that the subgraph , induced by , has maximum degree at most for . Let denote the family of plane graphs with neither adjacent 3‐cycles nor 5‐cycles. Borodin and Raspaud (2003) conjectured that each graph in is (0, 0, 0)‐colorable (which was disproved very recently). In this article, we prove that each graph in is (1, 1, 0)‐colorable, which improves the results by Xu (2009) and Liu‐Li‐Yu (2016).     

Thoroughly dispersed colorings

We consider (not necessarily proper) colorings of the vertices of a graph where every color is thoroughly dispersed, that is, appears in every open neighborhood. Equivalently, every color is a total dominating set. We define as the maximum number of colors in such a coloring and as the fractional version thereof. In particular, we show that every claw‐free graph with minimum degree at least  two has  and this is best possible. For planar graphs, we show that every triangular disc has and this is best possible, and that every planar graph has and this is best possible, while we conjecture that every planar triangulation has . Further, although there are arbitrarily large examples of connected, cubic graphs with , we show that for a connected cubic graph . We also consider the related concepts in hypergraphs.     

Ramsey Results for Cycle Spectra

Let denote the set of lengths of cycles of a graph G of order n and let denote the complement of G. We show that if , then contains all odd ? with and all even ? with , where and denote the maximum odd and the maximum even integer in , respectively. From this we deduce that the set contains at least integers, which is sharp.     

Dominating sets inducing large components in maximal outerplanar graphs

For a maximal outerplanar graph G of order n at least three, Matheson and Tarjan showed that G has domination number at most . Similarly, for a maximal outerplanar graph G of order n at least five, Dorfling, Hattingh, and Jonck showed, by a completely different approach, that G has total domination number at most unless G is isomorphic to one of two exceptional graphs of order 12. We present a unified proof of a common generalization of these two results. For every positive integer k, we specify a set of graphs of order at least and at most such that every maximal outerplanar graph G of order n at least that does not belong to has a dominating set D of order at most such that every component of the subgraph of G induced by D has order at least k.     

More on the Bipartite Decomposition of Random Graphs

For a graph , let denote the minimum number of pairwise edge disjoint complete bipartite subgraphs of G so that each edge of G belongs to exactly one of them. It is easy to see that for every graph G , , where is the maximum size of an independent set of G . Erd?s conjectured in the 80s that for almost every graph G equality holds, that is that for the random graph , with high probability, that is with probability that tends to 1 as n tends to infinity. The first author showed that this is slightly false, proving that for most values of n tending to infinity and for , with high probability. We prove a stronger bound: there exists an absolute constant so that with high probability.     

A Relaxed Version of the Erdős–Lovász Tihany Conjecture

The Erd?s–Lovász Tihany conjecture asserts that every graph G with ) contains two vertex disjoint subgraphs G ₁ and G ₂ such that and . Under the same assumption on G , we show that there are two vertex disjoint subgraphs G ₁ and G ₂ of G such that (a) and or (b) and . Here, is the chromatic number of is the clique number of G , and col(G ) is the coloring number of G .     

Non‐Critical Vertices and Long Circuits in Strong Tournaments of Order n and Diameter d

Let T be a strong tournament of order with diameter . A vertex w in T is non‐critical if the subtournament is also strong. In the opposite case, it is a critical vertex. In the present article, we show that T has at most critical vertices. This fact and Moon's vertex‐pancyclic theorem imply that for , it contains at least circuits of length . We describe the class of all strong tournaments of order with diameter for which this lower bound is achieved and show that for , the minimum number of circuits of length in a tournament of this class is equal to . In turn, the minimum among all strong tournaments of order with diameter 2 grows exponentially with respect to n for any given . Finally, for , we select a strong tournament of order n with diameter d and conjecture that for any strong tournament T of order n whose diameter does not exceed d, the number of circuits of length ? in T is not less than that in for each possible ?. Moreover, if these two numbers are equal to each other for some given , where , then T is isomorphic to either or its converse . For , this conjecture was proved by Las Vergnas. In the present article, we confirm it for the case . In an Appendix, some problems concerning non‐critical vertices are considered for generalizations of tournaments.     

Polychromatic colorings of complete graphs with respect to 1‐, 2‐factors and Hamiltonian cycles

If G is a graph and is a set of subgraphs of G, then an edge‐coloring of G is called ‐polychromatic if every graph from gets all colors present in G. The ‐polychromatic number of G, denoted , is the largest number of colors such that G has an ‐polychromatic coloring. In this article, is determined exactly when G is a complete graph and is the family of all 1‐factors. In addition is found up to an additive constant term when G is a complete graph and is the family of all 2‐factors, or the family of all Hamiltonian cycles.     

The complete bipartite graphs with a unique edge‐transitive embedding

Jones, Nedela, and Škoviera (2008) showed that a complete bipartite graph has a unique orientably regular embedding if and only if . In this article, we extend this result by proving that a complete bipartite graph has a unique orientably edge‐transitive embedding if and only if .     

Partition functions and a generalized coloring‐flow duality for embedded graphs

Let G be a finite group and a class function. Let be a directed graph with for each vertex a cyclic order of the edges incident to it. The cyclic orders give a collection F of faces of H. Define the partition function , where denotes the product of the κ‐values of the edges incident with v (in cyclic order), where the inverse is taken for edges leaving v. Write , where the sum runs over irreducible representations λ of G with character and with for every λ. When H is connected, it is proved that , where 1 is the identity element of G. Among the corollaries, a formula for the number of nowhere‐identity G‐flows on H is derived, generalizing a result of Tutte. We show that these flows correspond bijectively to certain proper G‐colorings of a covering graph of the dual graph of H. This correspondence generalizes coloring‐flow duality for planar graphs.     

Edge‐Disjoint Spanning Trees,Edge Connectivity,and Eigenvalues in Graphs

Let and denote the second largest eigenvalue and the maximum number of edge‐disjoint spanning trees of a graph G, respectively. Motivated by a question of Seymour on the relationship between eigenvalues of a graph G and bounds of , Cioab? and Wong conjectured that for any integers and a d‐regular graph G, if , then . They proved the conjecture for , and presented evidence for the cases when . Thus the conjecture remains open for . We propose a more general conjecture that for a graph G with minimum degree , if , then . In this article, we prove that for a graph G with minimum degree δ, each of the following holds.

• (i) For , if and , then .
• (ii) For , if and , then .

Our results sharpen theorems of Cioab? and Wong and give a partial solution to Cioab? and Wong's conjecture and Seymour's problem. We also prove that for a graph G with minimum degree , if , then the edge connectivity is at least k, which generalizes a former result of Cioab?. As corollaries, we investigate the Laplacian and signless Laplacian eigenvalue conditions on and edge connectivity.     

The decycling number and maximum genus of cubic graphs

Let and denote the minimum size of a decycling set and maximum genus of a graph G, respectively. For a connected cubic graph G of order n, it is shown that . Applying the formula, we obtain some new results on the decycling number and maximum genus of cubic graphs. Furthermore, it is shown that the number of vertices of a decycling set S in a k‐regular graph G is , where c and are the number of components of and the number of edges in , respectively. Therefore, S is minimum if and only if is minimum. As an application, this leads to a lower bound for of a k‐regular graph G. In many cases this bound may be sharp.     

Hamiltonicity and Degrees of Adjacent Vertices in Claw‐Free Graphs

For a graph H , let for every edge . For and , let be a set of k‐edge‐connected K₃‐free graphs of order at most r and without spanning closed trails. We show that for given and ε, if H is a k‐connected claw‐free graph of order n with and , and if n is sufficiently large, then either H is Hamiltonian or the Ryjác?ek's closure where G is an essentially k‐edge‐connected K₃‐free graph that can be contracted to a graph in . As applications, we prove:

• (i) For , if and if and n is sufficiently large, then H is Hamiltonian.
• (ii) For , if and n is sufficiently large, then H is Hamiltonian.

These bounds are sharp. Furthermore, since the graphs in are fixed for given p and can be determined in a constant time, any improvement to (i) or (ii) by increasing the value of p and so enlarging the number of exceptions can be obtained computationally.     

Packing Countably Many Branchings with Prescribed Root‐Sets in Infinite Digraphs

We generalize an unpublished result of C. Thomassen. Let be a digraph and let be a multiset of subsets of V in such a way that any backward‐infinite path in D meets all the sets . We show that if all is simultaneously reachable from the sets by edge‐disjoint paths, then there exists a system of edge‐disjoint spanning branchings in D where the root‐set of is .     

On the Structure of Graphs with Given Odd Girth and Large Minimum Degree

We study minimum degree conditions for which a graph with given odd girth has a simple structure. For example, the classical work of Andrásfai, Erd?s, and Sós implies that every n‐vertex graph with odd girth and minimum degree bigger than must be bipartite. We consider graphs with a weaker condition on the minimum degree. Generalizing results of Häggkvist and of Häggkvist and Jin for the cases and 3, we show that every n‐vertex graph with odd girth and minimum degree bigger than is homomorphic to the cycle of length . This is best possible in the sense that there are graphs with minimum degree and odd girth that are not homomorphic to the cycle of length . Similar results were obtained by Brandt and Ribe‐Baumann.