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.     

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.     

A sufficient condition for the existence of an anti-directed 2-factor in a directed graph

Let D be a directed graph with vertex set V, arc set A, and order n. The graph underlyingD is the graph obtained from D by replacing each arc (u,v)∈A by an undirected edge {u,v} and then replacing each double edge by a single edge. An anti-directed (hamiltonian) cycleH in D is a (hamiltonian) cycle in the graph underlying D such that no pair of consecutive arcs in H form a directed path in D. An anti-directed 2-factor in D is a vertex-disjoint collection of anti-directed cycles in D that span V. It was proved in Busch et al. (submitted for publication) [3] that if the indegree and the outdegree of each vertex of D is greater than then D contains an anti-directed Hamilton cycle. In this paper we prove that given a directed graph D, the problem of determining whether D has an anti-directed 2-factor is NP-complete, and we use a proof technique similar to the one used in Busch et al. (submitted for publication) [3] to prove that if the indegree and the outdegree of each vertex of D is greater than then D contains an anti-directed 2-factor.     

Finite cubic graphs admitting a cyclic group of automorphism with at most three orbits on vertices

The theory of voltage graphs has become a standard tool in the study of graphs admitting a semiregular group of automorphisms. We introduce the notion of a cyclic generalised voltage graph to extend the scope of this theory to graphs admitting a cyclic group of automorphisms that may not be semiregular. We use this new tool to classify all cubic graphs admitting a cyclic group of automorphisms with at most three vertex-orbits and we characterise vertex-transitivity for each of these classes. In particular, we show that a cubic vertex-transitive graph admitting a cyclic group of automorphisms with at most three orbits on vertices either belongs to one of 5 infinite families or is isomorphic to the well-known Tutte–Coxeter graph.     

A 4/3-approximation for TSP on cubic 3-edge-connected graphs

For a 3-edge-connected cubic graph $G=(V,E)$, we give an algorithm to construct a connected Eulerian subgraph of $2G$ using at most $?4\left|V\right|∕3?$ edges.     

Independent domination in subcubic graphs of girth at least six

A set $S$ of vertices in a graph $G$ is an independent dominating set of $G$ if $S$ is an independent set and every vertex not in $S$ is adjacent to a vertex in $S$. The independent domination number, $i\left(G\right)$, of $G$ is the minimum cardinality of an independent dominating set. In this paper, we extend the work of Henning, Löwenstein, and Rautenbach (2014) who proved that if $G$ is a bipartite, cubic graph of order $n$ and of girth at least $6$, then $i\left(G\right)\le \frac{4}{11}n$. We show that the bipartite condition can be relaxed, and prove that if $G$ is a cubic graph of order $n$ and of girth at least $6$, then $i\left(G\right)\le \frac{4}{11}n$.     

On 2-factors with cycles containing specified edges in a bipartite graph

Let k≥1 be an integer and G=(V₁,V₂;E) a bipartite graph with |V₁|=|V₂|=n such that n≥2k+2. In this paper it has been proved that if for each pair of nonadjacent vertices x∈V₁ and y∈V₂, , then for any k independent edges e₁,…,e_k of G, G has a 2-factor with k+1 cycles C₁,…,C_k+1 such that e_i∈E(C_i) and |V(C_i)|=4 for each i∈{1,…,k}. We shall also show that the conditions in this paper are sharp.     

Partition into cliques for cubic graphs: Planar case, complexity and approximation

Given a graph G=(V,E) and a positive integer k, the partition into cliques (pic) decision problem consists of deciding whether there exists a partition of V into k disjoint subsets V₁,V₂,…,V_k such that the subgraph induced by each part V_i is a complete subgraph (clique) of G. In this paper, we establish both the NP-completeness of pic for planar cubic graphs and the Max SNP-hardness of pic for cubic graphs. We present a deterministic polynomial time -approximation algorithm for finding clique partitions in maximum degree three graphs.