Decomposition of cubic graphs with cyclic connectivity 5

Let G be a cyclically 5-connected cubic graph with a 5-edge-cut separating G into two cyclic components $G_1$ and $G_2$. We prove that each component $G_i$ can be completed to a cyclically 5-connected cubic graph by adding three vertices, unless $G_i$ is a cycle of length five. Our work extends similar results by Andersen et al. for cyclic connectivity 4 from 1988.     

Line-graphs of cubic graphs are normal

A graph is called normal if its vertex set can be covered by cliques Q₁,Q₂,…,Q_k and also by stable sets S₁,S₂,…,S_l, such that S_i∩Q_j≠∅ for every i,j. This notion is due to Körner, who introduced the class of normal graphs as an extension of the class of perfect graphs. Normality has also relevance in information theory. Here we prove, that the line graphs of cubic graphs are normal.     

On isomorphic linear partitions in cubic graphs

A linear forest is a graph whose connected components are chordless paths. A linear partition of a graph G is a partition of its edge set into linear forests and la(G) is the minimum number of linear forests in a linear partition. It is well known that la(G)=2 when G is a cubic graph and Wormald [N. Wormald, Problem 13, Ars Combinatoria 23(A) (1987) 332-334] conjectured that if |V(G)|≡0 (mod 4), then it is always possible to find a linear partition in two isomorphic linear forests. Here, we give some new results concerning this conjecture.     

Closure, stability and iterated line graphs with a 2-factor

We consider 2-factors with a bounded number of components in the n-times iterated line graph Lⁿ(G). We first give a characterization of graph G such that Lⁿ(G) has a 2-factor containing at most k components, based on the existence of a certain type of subgraph in G. This generalizes the main result of [L. Xiong, Z. Liu, Hamiltonian iterated line graphs, Discrete Math. 256 (2002) 407-422]. We use this result to show that the minimum number of components of 2-factors in the iterated line graphs Lⁿ(G) is stable under the closure operation on a claw-free graph G. This extends results in [Z. Ryjá?ek, On a closure concept in claw-free graphs, J. Combin. Theory Ser. B 70 (1997) 217-224; Z. Ryjá?ek, A. Saito, R.H. Schelp, Closure, 2-factors and cycle coverings in claw-free graphs, J. Graph Theory 32 (1999) 109-117; L. Xiong, Z. Ryjá?ek, H.J. Broersma, On stability of the hamiltonian index under contractions and closures, J. Graph Theory 49 (2005) 104-115].     

Packing chromatic number of cubic graphs

A packing$k$-coloring of a graph $G$ is a partition of $V\left(G\right)$ into sets $V_1,\dots ,V_k$ such that for each $1\le i\le k$ the distance between any two distinct $x,y\in V_i$ is at least $i+1$. The packing chromatic number, ${\chi }_p\left(G\right)$, of a graph $G$ is the minimum $k$ such that $G$ has a packing $k$-coloring. Sloper showed that there are $4$-regular graphs with arbitrarily large packing chromatic number. The question whether the packing chromatic number of subcubic graphs is bounded appears in several papers. We answer this question in the negative. Moreover, we show that for every fixed $k$ and $g\ge 2k+2$, almost every $n$-vertex cubic graph of girth at least $g$ has the packing chromatic number greater than $k$.     

The asymptotic number of claw-free cubic graphs

Let H_n be the number of claw-free cubic graphs on 2n labeled nodes. In an earlier paper we characterized claw-free cubic graphs and derived a recurrence relation for H_n. Here we determine the asymptotic behavior of this sequence:

     

An infinite family of cubic nonnormal Cayley graphs on nonabelian simple groups

We construct a connected cubic nonnormal Cayley graph on ${\mathrm{A}}_{2^m?1}$ for each integer $m?4$ and determine its full automorphism group. This is the first infinite family of connected cubic nonnormal Cayley graphs on nonabelian simple groups.     

Oddness to resistance ratios in cubic graphs

Let $G$ be a bridgeless cubic graph. Oddness (weak oddness) is defined as the minimum number of odd components in a 2-factor (an even factor) of $G$, denoted as $\omega \left(G\right)$ (Steffen, 2004) (${\omega }^{\prime }\left(G\right)$ Lukot’ka and Mazák (2016)). Oddness and weak oddness have been referred to as measurements of uncolourability (Fiol et al., 2017, Lukot’ka and Mazák, 2016, Lukot’ka et al., 2015 and, Steffen, 2004), due to the fact that $\omega \left(G\right)=0$ and ${\omega }^{\prime }\left(G\right)=0$ if and only if $G$ is 3-edge-colourable. Another so-called measurement of uncolourability is resistance, defined as the minimum number of edges that can be removed from $G$ such that the resulting graph is 3-edge-colourable, denoted as $r\left(G\right)$ (Steffen, 2004). It is easily shown that $\omega \left(G\right)\ge {\omega }^{\prime }\left(G\right)\ge r\left(G\right)$. While it has been shown that the difference between any two of these measures can be arbitrarily large, it has been conjectured that ${\omega }^{\prime }\left(G\right)\le 2r\left(G\right)$, and that if $G$ is a snark then $\omega \left(G\right)\le 2r\left(G\right)$ (Fiol et al., 2017). In this paper, we disprove the latter by showing that the ratio of oddness to weak oddness can be arbitrarily large. We also offer some insights into the former conjecture by defining what we call resistance reducibility, and hypothesizing that almost all cubic graphs are such resistance reducible.     

Subdivisions of graphs: A generalization of paths and cycles

One of the basic results in graph theory is Dirac's theorem, that every graph of order n?3 and minimum degree ?n/2 is Hamiltonian. This may be restated as: if a graph of order n and minimum degree ?n/2 contains a cycle C then it contains a spanning cycle, which is just a spanning subdivision of C. We show that the same conclusion is true if instead of C, we choose any graph H such that every connected component of H is non-trivial and contains at most one cycle. The degree bound can be improved to (n-t)/2 if H has t components that are trees.We attempt a similar generalization of the Corrádi-Hajnal theorem that every graph of order ?3k and minimum degree ?2k contains k disjoint cycles. Again, this may be restated as: every graph of order ?3k and minimum degree ?2k contains a subdivision of kK₃. We show that if H is any graph of order n with k components, each of which is a cycle or a non-trivial tree, then every graph of order ?n and minimum degree ?n-k contains a subdivision of H.     

New conjectures on perfect matchings in cubic graphs

We propose three new conjectures on perfect matchings in cubic graphs. The weakest conjecture is implied by a well-known conjecture of Berge and Fulkerson. The other two conjectures are a strengthening of the first one. All conjectures are trivially verified for 3-edge-colorable cubic graphs and by computer for all snarks of order at most 34.     

1-factor covers of regular graphs

We consider minimal 1-factor covers of regular multigraphs, focusing on those that are 1-factorizations. In particular, we classify cubic graphs such that every minimal 1-factor cover is also a 1-factorization, and also classify simple regular bipartite graphs with this property. For r>3, we show that there are finitely many simple r-regular graphs such that every minimal 1-factor cover is also a 1-factorization.     

Highly-connected planar cubic graphs with few or many Hamilton cycles

In this paper we consider the number of Hamilton cycles in planar cubic graphs of high cyclic edge-connectivity, answering two questions raised by Chia and Thomassen (2012) about extremal graphs in these families. In particular, we find families of cyclically 5-edge-connected planar cubic graphs with more Hamilton cycles than the generalized Petersen graphs $P(2n,2)$. The graphs themselves are fullerene graphs that correspond to certain carbon molecules known as nanotubes—more precisely, the family consists of the zigzag nanotubes of (fixed) width 5and increasing length. In order to count the Hamilton cycles in the nanotubes, we develop methods inspired by the transfer matrices of statistical physics. We outline how these methods can be adapted to count the Hamilton cycles in nanotubes of greater (but still fixed) width, with the caveat that the resulting expressions involve matrix powers. We also consider cyclically 4-edge-connected planar cubic graphs with few Hamilton cycles, and exhibit an infinite family of such graphs each with exactly 4 Hamilton cycles. Finally we consider the “other extreme” for these two classes of graphs, thus investigating cyclically 4-edge-connected planar cubic graphs with many Hamilton cycles and the cyclically 5-edge-connected planar cubic graphs with few Hamilton cycles. In each of these cases, we present partial results, examples and conjectures regarding the graphs with few or many Hamilton cycles.     

Pairs and triples of forbidden subgraphs and the existence of a 2-factor

Let be a set of connected graphs, each of which has order at least three, and suppose that there exist infinitely many connected -free graphs of minimum degree at least  two and all except for finitely many of them have a 2-factor. In [J. Graph Theory, 64 (2010), 250–266], we proved that if , then one of the members in is a star. In this article, we determine the remaining members of and hence give a complete characterization of the pairs and triples of forbidden subgraphs.