# On a family of cubic graphs containing the flower snarks

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

Discussiones Mathematicae Graph Theory (2010)

- Volume: 30, Issue: 2, page 289-314
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topJean-Luc Fouquet, Henri Thuillier, and Jean-Marie Vanherpe. "On a family of cubic graphs containing the flower snarks." Discussiones Mathematicae Graph Theory 30.2 (2010): 289-314. <http://eudml.org/doc/270839>.

@article{Jean2010,

abstract = {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.},

author = {Jean-Luc Fouquet, Henri Thuillier, Jean-Marie Vanherpe},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {cubic graph; perfect matching; strong matching; counting; hamiltonian cycle; 2-factor hamiltonian; Hamiltonian cycle; 2-factor Hamiltonian},

language = {eng},

number = {2},

pages = {289-314},

title = {On a family of cubic graphs containing the flower snarks},

url = {http://eudml.org/doc/270839},

volume = {30},

year = {2010},

}

TY - JOUR

AU - Jean-Luc Fouquet

AU - Henri Thuillier

AU - Jean-Marie Vanherpe

TI - On a family of cubic graphs containing the flower snarks

JO - Discussiones Mathematicae Graph Theory

PY - 2010

VL - 30

IS - 2

SP - 289

EP - 314

AB - 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.

LA - eng

KW - cubic graph; perfect matching; strong matching; counting; hamiltonian cycle; 2-factor hamiltonian; Hamiltonian cycle; 2-factor Hamiltonian

UR - http://eudml.org/doc/270839

ER -

## References

top- [1] M. Abreu, A.A. Diwan, B. Jackson, D. Labbate and J. Sheehan, Pseudo 2-factor isomorphic regular bipartite graphs, J. Combin. Theory (B) 98 (2008) 432-442, doi: 10.1016/j.jctb.2007.08.006. Zbl1134.05079
- [2] S. Bonvicini and G. Mazzuoccolo, On perfectly one-factorable cubic graphs, Electronic Notes in Discrete Math. 24 (2006) 47-51, doi: 10.1016/j.endm.2006.06.008. Zbl1201.05044
- [3] J.-L. Fouquet, H. Thuillier, J.-M. Vanherpe and A.P. Wojda, On linear arboricity of cubic graphs, LIFO Univ. d'Orlans - Research Report 13 (2007) 1-28.
- [4] J.-L. Fouquet, H. Thuillier, J.-M. Vanherpe and A.P. Wojda, On isomorphic linear partition in cubic graphs, Discrete Math. 309 (2009) 6425-6433, doi: 10.1016/j.disc.2008.10.017. Zbl1218.05130
- [5] D.R. Fulkerson, Blocking and anti-blocking pairs of polyhedra, Math. Programming 1 (1971) 168-194, doi: 10.1007/BF01584085. Zbl0254.90054
- [6] M. Funk, B. Jackson, D. Labbate and J. Sheehan, 2-factor hamiltonian graphs, J. Combin. Theory (B) 87 (2003) 138-144, doi: 10.1016/S0095-8956(02)00031-X. Zbl1045.05061
- [7] M. Funk and D. Labbate, On minimally one-factorable r-regular bipartite graphs, Discrete Math. 216 (2000) 121-137, doi: 10.1016/S0012-365X(99)00241-1. Zbl0952.05055
- [8] R. Isaacs, Infinite families of non-trivial trivalent graphs which are not Tait colorable, Am. Math. Monthly 82 (1975) 221-239, doi: 10.2307/2319844. Zbl0311.05109
- [9] F. Jaeger, Etude de quelques invariants et problèmes d'existence en théorie de graphes (Thèse d'État, IMAG, Grenoble, 1976).
- [10] A. Kotzig, Balanced colourings and the four colour conjecture, in: Proc. Sympos. Smolenice, 1963, Publ. House Czechoslovak Acad. Sci. (Prague, 1964) 63-82.
- [11] A. Kotzig, Construction for Hamiltonian graphs of degree three (in Russian), Cas. pest. mat. 87 (1962) 148-168.
- [12] A. Kotzig and J. Labelle, Quelques problmes ouverts concernant les graphes fortement hamiltoniens, Ann. Sci. Math. Qubec 3 (1979) 95-106. Zbl0404.05043
- [13] D. Labbate, On 3-cut reductions of minimally 1-factorable cubic bigraphs, Discrete Math. 231 (2001) 303-310, doi: 10.1016/S0012-365X(00)00327-7. Zbl0979.05089
- [14] D. Labbate, Characterizing minimally 1-factorable r-regular bipartite graphs, Discrete Math. 248 (2002) 109-123, doi: 10.1016/S0012-365X(01)00189-3. Zbl0994.05123
- [15] N. Robertson and P. Seymour, Excluded minor in cubic graphs, (announced), see also www.math.gatech.edu/thomas/OLDFTP/cubic/graphs.
- [16] P. Seymour, On multi-colourings of cubic graphs, and conjectures of Fulkerson and Tutte, Proc. London Math. Soc. 38 (1979) 423-460, doi: 10.1112/plms/s3-38.3.423. Zbl0411.05037

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.