On a family of cubic graphs containing the flower snarks

Jean-Luc Fouquet ; Henri Thuillier ; Jean-Marie Vanherpe

Discussiones Mathematicae Graph Theory, Tome 30 (2010) no. 2, p. 289.

Résumé

We consider cubic graphs formed with k ≥ 2 disjoint claws C i K 1 , 3 (0 ≤ i ≤ k-1) such that for every integer i modulo k the three vertices of degree 1 of C i are joined to the three vertices of degree 1 of C i - 1 and joined to the three vertices of degree 1 of C i + 1 . Denote by t i the vertex of degree 3 of C i and by T the set t ₁ , t ₂ , . . . , t k - 1 . In such a way we construct three distinct graphs, namely FS(1,k), FS(2,k) and FS(3,k). The graph FS(j,k) (j ∈ 1,2,3) is the graph where the set of vertices ⋃ i = 0 i = k - 1 V ( C i ) ∖ T induce j cycles (note that the graphs FS(2,2p+1), p ≥ 2, are the flower snarks defined by Isaacs [8]). We determine the number of perfect matchings of every FS(j,k). A cubic graph G is said to be 2-factor hamiltonian if every 2-factor of G is a hamiltonian cycle. We characterize the graphs FS(j,k) that are 2-factor hamiltonian (note that FS(1,3) is the “Triplex Graph” of Robertson, Seymour and Thomas [15]). A strong matching M in a graph G is a matching M such that there is no edge of E(G) connecting any two edges of M. A cubic graph having a perfect matching union of two strong matchings is said to be a Jaeger’s graph. We characterize the graphs FS(j,k) that are Jaeger’s graphs.

Détail

Classification : 05C45, 05C70
Mots-clés : cubic graph, perfect matching, strong matching, counting, hamiltonian cycle, 2-factor hamiltonian, Hamiltonian cycle, 2-factor Hamiltonian