On a family of cubic graphs containing the flower snarks

Abstract

We consider cubic graphs formed with $k\ge 2$ disjoint claws $C_i\sim K_{1,3}$ ($0\le i\le 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_1,t_2,...,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\in \{1,2,3\}$) is the graph where the set of vertices ${\cup }_{i=0}^{i=k-1}V(C_i)\setminus T$ induce $j$ cycles (note that the graphs $FS(2,2p+1)$, $p\ge 2$, are the flower snarks defined by Isaacs \cite{Isa75}). We determine the number of perfect matchings of every $FS(j,k)$. A cubic graph $G$ is said to be {\em 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 \cite{RobSey}). A {\em 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 {\em\Jaev}. We characterize the graphs $FS(j,k)$ that are \Jaesv.

Cited by in corpus (1)

• Odd 2-factored snarks