×
Lo, On-Hei S.; Schmidt, Jens M.; Van Cleemput, Nico; Zamfirescu, Carol T.

Shortness coefficient of cyclically 4-edge-connected cubic graphs. (English) Zbl 1432.05059

Electron. J. Comb. 27, No. 1, Research Paper P1.43, 14 p. (2020).
Summary: B. Grünbaum and J. Malkevitch [Aequationes Math. 14, 191–196 (1976; Zbl 0331.05118)] proved that the shortness coefficient of cyclically 4-edge-connected cubic planar graphs is at most \(\frac{76}{77}\). Recently, this was improved to \(\frac{359}{366}\) \((<\frac{52}{53})\) and the question was raised whether this can be strengthened to \(\frac{41}{42}\), a natural bound inferred from one of the Faulkner-Younger graphs. We prove that the shortness coefficient of cyclically 4-edge-connected cubic planar graphs is at most \(\frac{37}{38}\) and that we also get the same value for cyclically 4-edge-connected cubic graphs of genus \(g\) for any prescribed genus \(g \geqslant 0\). We also show that \(\frac{45}{46}\) is an upper bound for the shortness coefficient of cyclically 4-edge-connected cubic graphs of genus \(g\) with face lengths bounded above by some constant larger than 22 for any prescribed \(g \geqslant 0\).

Cited in 1 Document

MSC:

05C40 Connectivity
05C38 Paths and cycles
05C45 Eulerian and Hamiltonian graphs
05C10 Planar graphs; geometric and topological aspects of graph theory

Citations:

Zbl 0331.05118
PDF BibTeX XML Cite
\textit{O.-H. S. Lo} et al., Electron. J. Comb. 27, No. 1, Research Paper P1.43, 14 p. (2020; Zbl 1432.05059)
Full Text: DOI Link

References:

[1] R. E. L. Aldred, S. Bau, D. A. Holton, and B. D. McKay.Nonhamiltonian 3connected cubic planar graphs.SIAM J. Discrete Math., 13(1):25-32, 2000. · Zbl 0941.05041
[2] J. A. Bondy and M. Simonovits. Longest cycles in 3-connected 3-regular graphs. Canad. J. Math., 32:987-992, 1980. · Zbl 0454.05043
[3] G. Brinkmann and B. McKay. Fast generation of planar graphs.MATCH Commun. Math. Comput. Chem., 42(4):909-924, 2007.Seehttp://cs.anu.edu.au/  bdm/index.html.
[4] G. Brinkmann and C. T. Zamfirescu. Polyhedra with few 3-cuts are hamiltonian. Electr. J. Combin., 26:#P1.39, 2019. · Zbl 1409.05122
[5] G. Chen and X. Yu. Long cycles in 3-connected graphs.J. Combin. Theory, Ser. B, 86(1):80-99, 2002. · Zbl 1025.05036
[6] V. Chv´atal. Flip-flops in hypohamiltonian graphs.Canad. Math. Bull., 16:33-41, 1973. · Zbl 0253.05142
[7] I. Fabrici, J. Harant, T. Madaras, S. Mohr, R. Sot´ak, and C. T. Zamfirescu. Long cycles and spanning subgraphs of locally maximal 1-planar graphs. To appear inJ. Graph Theory. Manuscript available online athttps://arxiv.org/abs/1912.08028, 2018.
[8] G. B. Faulkner and D. H. Younger. Non-Hamiltonian cubic planar maps.Discrete Math., 7(1-2):67-74, 1974. · Zbl 0271.05106
[9] H. Fleischner and B. Jackson. A note concerning some conjectures on cyclically 4edge connected 3-regular graphs.Graph Theory in Memory of G. A. Dirac (ed.: L. D. Andersen), Annals Discrete Math., 41:171-177, 1988.
[10] E. J. Grinberg. Plane homogeneous graphs of degree three without Hamiltonian circuits (in Russian).Latvian Math. Yearbook, 4:51-58, 1968. · Zbl 0185.27901
[11] B. Gr¨unbaum and J. Malkevitch. Pairs of edge-disjoint Hamiltonian circuits.Aequat. Math., 14(1):191-196, 1976. · Zbl 0331.05118
[12] B. Gr¨unbaum and H. Walther. Shortness exponents of families of graphs.J. Combin. Theory, Ser. A, 14(3):364-385, 1973. · Zbl 0263.05103
[13] J. H¨agglund. On snarks that are far from being 3-edge colorable.Electr. J. Combin., 23:#P2.6, 2016.
[14] J. Harant.Uber den Shortness Exponent regul¨¨arer Polyedergraphen mit genau zwei Typen von Elementarfl¨achen (in German). PhD thesis, Technische Hochschule Ilmenau, 1982.
[15] J. Harant and H. Walther. Some new results about the shortness exponent in polyhedral graphs.Casopis pro pˇˇestov´an´ı matematiky, 112(2):114-122, 1987. · Zbl 0642.05039
[16] Q. Liu, X. Yu, and Z. Zhang. Circumference of 3-connected cubic graphs.J. Combin. Theory, Ser. B, 128:134-159, 2018. · Zbl 1375.05157
[17] O.-H. S. Lo and J. M. Schmidt. Longest cycles in cyclically 4-edge-connected cubic planar graphs.Australas. J. Combin., 72(1):155-162, 2018. · Zbl 1405.05046
[18] K. Markstr¨om. Improved bounds for the shortness coefficient of cyclically 4-edge connected cubic graphs and snarks. Manuscript available online atarXiv:1309.3870, 2014.
[19] E. M´aˇcajov´a and J. Maz´ak. Cubic graphs with large circumference deficit.J. Graph Theory, 82(4):433-440, 2016.
[20] J. W. Moon and L. Moser. Simple paths on polyhedra.Pacific J. Math., 13(2):629- 631, 1963. · Zbl 0115.41001
[21] P. J. Owens. Regular planar graphs with faces of only two types and shortness parameters.J. Graph Theory, 8:253-275, 1984. · Zbl 0541.05037
[22] K. Ozeki, N. Van Cleemput, and C. T. Zamfirescu. Hamiltonian properties of polyhedra with few 3-cuts – a survey.Discrete Math., 341(9):2646 - 2660, 2018. · Zbl 1392.05066
[23] E. Steinitz. Polyeder und Raumeinteilungen.Encyklop¨adie der mathematischen Wissenschaften, Band 3 (Geometrie):1-139, 1922.
[24] C. Thomassen. A theorem on paths in planar graphs.J. Graph Theory, 7(2):169-176, 1983. · Zbl 0515.05040
[25] C. Thomassen. Reflections on graph theory.J. Graph Theory, 10(3):309-324, 1986. · Zbl 0614.05050
[26] W. T. Tutte. A theorem on planar graphs.Trans. Amer. Math. Soc., 82(1):99-116, 1956. · Zbl 0070.18403
[27] H. Walther. ¨Uber Extremalkreise in regul¨aren Landkarten.Wiss. Z. Techn. Hochsch. Ilmenau, 15:139-142, 1969. · Zbl 0202.23402
[28] H. Walther. Polyhedral graphs without hamiltonian cycles.Discrete Appl. Math., 79(1):257-263, 1997. · Zbl 0883.05092
[29] J. Zaks. Non-hamiltonian simple 3-potytopes having just two types of faces.Discrete Math., 29:87-101, 1980. · Zbl 0445.05065
[30] J. Zaks. Shortness coefficient of cyclically 5-connected cubic planar graphs.Aequat. Math., 25:97-102, 1982. · Zbl 0518.05045
[31] C.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.