Shortness coefficient of cyclically 4-edge-connected cubic graphs

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

doi:10.37236/8440

Shortness coefficient of cyclically 4-edge-connected cubic graphs

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

Research output: Contribution to journal › Article › peer-review

2 Citations (Scopus)

1 Downloads (Pure)

Abstract

Grünbaum and Malkevitch proved that the shortness coefficient of cyclically 4-edge-connected cubic planar graphs is at most⁷⁶ 77. Recently, this was improved to (Formula Presented) and the question was raised whether this can be strengthened to 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 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 ≥ 0. We also show that⁴⁵ 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 ≥ 0.

Original language	English
Article number	P1.43
Number of pages	14
Journal	The Electronic Journal of Combinatorics
Volume	27
Issue number	1
DOIs	https://doi.org/10.37236/8440
Publication status	Published - Feb 2020
Externally published	Yes

Bibliographical note

Publisher Copyright:
© The authors.

Access to Document

10.37236/8440Licence: CC BY-ND

Full textFinal published version, 390 KBLicence: CC BY-ND

Cite this

@article{f24a3284e81143f7a5ebe807989aa66e,

title = "Shortness coefficient of cyclically 4-edge-connected cubic graphs",

abstract = "Gr{\"u}nbaum and Malkevitch proved that the shortness coefficient of cyclically 4-edge-connected cubic planar graphs is at most76 77. Recently, this was improved to (Formula Presented) and the question was raised whether this can be strengthened to 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 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 ≥ 0. We also show that45 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 ≥ 0.",

author = "Lo, {On-Hei S} and Schmidt, {Jens M.} and {Van Cleemput}, Nico and Zamfirescu, {Carol T.}",

note = "Publisher Copyright: {\textcopyright} The authors.",

year = "2020",

month = feb,

doi = "10.37236/8440",

language = "English",

volume = "27",

journal = "The Electronic Journal of Combinatorics",

number = "1",

}

TY - JOUR

T1 - Shortness coefficient of cyclically 4-edge-connected cubic graphs

AU - Lo, On-Hei S

AU - Schmidt, Jens M.

AU - Van Cleemput, Nico

AU - Zamfirescu, Carol T.

PY - 2020/2

Y1 - 2020/2

N2 - Grünbaum and Malkevitch proved that the shortness coefficient of cyclically 4-edge-connected cubic planar graphs is at most76 77. Recently, this was improved to (Formula Presented) and the question was raised whether this can be strengthened to 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 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 ≥ 0. We also show that45 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 ≥ 0.

AB - Grünbaum and Malkevitch proved that the shortness coefficient of cyclically 4-edge-connected cubic planar graphs is at most76 77. Recently, this was improved to (Formula Presented) and the question was raised whether this can be strengthened to 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 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 ≥ 0. We also show that45 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 ≥ 0.

U2 - 10.37236/8440

DO - 10.37236/8440

M3 - Article

VL - 27

JO - The Electronic Journal of Combinatorics

JF - The Electronic Journal of Combinatorics

IS - 1

M1 - P1.43

ER -

Shortness coefficient of cyclically 4-edge-connected cubic graphs

Abstract

Bibliographical note

Access to Document

Fingerprint

Cite this