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

Abstract

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

How to cite

top

Jean-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. [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. [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. [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. [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. [5] D.R. Fulkerson, Blocking and anti-blocking pairs of polyhedra, Math. Programming 1 (1971) 168-194, doi: 10.1007/BF01584085. Zbl0254.90054
  6. [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. [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. [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. [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. [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. [11] A. Kotzig, Construction for Hamiltonian graphs of degree three (in Russian), Cas. pest. mat. 87 (1962) 148-168. 
  12. [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. [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. [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. [15] N. Robertson and P. Seymour, Excluded minor in cubic graphs, (announced), see also www.math.gatech.edu/thomas/OLDFTP/cubic/graphs. 
  16. [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 ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.