On a family of cubic graphs containing the flower snarks

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

Discussiones Mathematicae. Graph Theory, Tome 30 (2010) no. 2, pp. 289-314

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

Keywords: cubic graph, perfect matching, strong matching, counting, hamiltonian cycle, 2-factor hamiltonian