Advanced search
1 file | 365.86 KB Add to list

Smallest snarks with oddness 4 and cyclic connectivity 4 have order 44

(2019) ARS MATHEMATICA CONTEMPORANEA. 16(2). p.277-298
Author
Organization
Project
Abstract
The family of snarks - connected bridgeless cubic graphs that cannot be 3-edge-coloured - is well-known as a potential source of counterexamples to several important and long-standing conjectures in graph theory. These include the cycle double cover conjecture, Tutte's 5-flow conjecture, Fulkerson's conjecture, and several others. One way of approaching these conjectures is through the study of structural properties of snarks and construction of small examples with given properties. In this paper we deal with the problem of determining the smallest order of a nontrivial snark (that is, one which is cyclically 4-edge-connected and has girth at least 5) of oddness at least 4. Using a combination of structural analysis with extensive computations we prove that the smallest order of a snark with oddness at least 4 and cyclic connectivity 4 is 44. Formerly it was known that such a snark must have at least 38 vertices and one such snark on 44 vertices was constructed by Lukot' ka, Macajova, Mazak and Skoviera in 2015. The proof requires determining all cyclically 4-edge-connected snarks on 36 vertices, which extends the previously compiled list of all such snarks up to 34 vertices. As a by-product, we use this new list to test the validity of several conjectures where snarks can be smallest counterexamples.
Keywords
Cubic graph, cyclic connectivity, edge-colouring, snark, oddness, computation, DOUBLE COVERS, CUBIC GRAPHS, EDGES

Downloads

  • 1601-8052-1-PB.pdf
    • full text
    • |
    • open access
    • |
    • PDF
    • |
    • 365.86 KB

Citation

Please use this url to cite or link to this publication:

MLA
Goedgebeur, Jan, et al. “Smallest Snarks with Oddness 4 and Cyclic Connectivity 4 Have Order 44.” ARS MATHEMATICA CONTEMPORANEA, vol. 16, no. 2, 2019, pp. 277–98.
APA
Goedgebeur, J., Máčajová, E., & Škoviera, M. (2019). Smallest snarks with oddness 4 and cyclic connectivity 4 have order 44. ARS MATHEMATICA CONTEMPORANEA, 16(2), 277–298.
Chicago author-date
Goedgebeur, Jan, Edita Máčajová, and Martin Škoviera. 2019. “Smallest Snarks with Oddness 4 and Cyclic Connectivity 4 Have Order 44.” ARS MATHEMATICA CONTEMPORANEA 16 (2): 277–98.
Chicago author-date (all authors)
Goedgebeur, Jan, Edita Máčajová, and Martin Škoviera. 2019. “Smallest Snarks with Oddness 4 and Cyclic Connectivity 4 Have Order 44.” ARS MATHEMATICA CONTEMPORANEA 16 (2): 277–298.
Vancouver
1.
Goedgebeur J, Máčajová E, Škoviera M. Smallest snarks with oddness 4 and cyclic connectivity 4 have order 44. ARS MATHEMATICA CONTEMPORANEA. 2019;16(2):277–98.
IEEE
[1]
J. Goedgebeur, E. Máčajová, and M. Škoviera, “Smallest snarks with oddness 4 and cyclic connectivity 4 have order 44,” ARS MATHEMATICA CONTEMPORANEA, vol. 16, no. 2, pp. 277–298, 2019.
@article{8637147,
  abstract     = {The family of snarks - connected bridgeless cubic graphs that cannot be 3-edge-coloured - is well-known as a potential source of counterexamples to several important and long-standing conjectures in graph theory. These include the cycle double cover conjecture, Tutte's 5-flow conjecture, Fulkerson's conjecture, and several others. One way of approaching these conjectures is through the study of structural properties of snarks and construction of small examples with given properties. In this paper we deal with the problem of determining the smallest order of a nontrivial snark (that is, one which is cyclically 4-edge-connected and has girth at least 5) of oddness at least 4. Using a combination of structural analysis with extensive computations we prove that the smallest order of a snark with oddness at least 4 and cyclic connectivity 4 is 44. Formerly it was known that such a snark must have at least 38 vertices and one such snark on 44 vertices was constructed by Lukot' ka, Macajova, Mazak and Skoviera in 2015. The proof requires determining all cyclically 4-edge-connected snarks on 36 vertices, which extends the previously compiled list of all such snarks up to 34 vertices. As a by-product, we use this new list to test the validity of several conjectures where snarks can be smallest counterexamples.},
  author       = {Goedgebeur, Jan and Máčajová, Edita and Škoviera, Martin},
  issn         = {1855-3966},
  journal      = {ARS MATHEMATICA CONTEMPORANEA},
  keywords     = {Cubic graph,cyclic connectivity,edge-colouring,snark,oddness,computation,DOUBLE COVERS,CUBIC GRAPHS,EDGES},
  language     = {eng},
  number       = {2},
  pages        = {277--298},
  title        = {Smallest snarks with oddness 4 and cyclic connectivity 4 have order 44},
  url          = {http://dx.doi.org/10.26493/1855-3974.1601.e75},
  volume       = {16},
  year         = {2019},
}

Altmetric
View in Altmetric
Web of Science
Times cited: