Quest for graphs of Frank number 3

Barát, János and Blázsik, Zoltán (2024) Quest for graphs of Frank number 3. AUSTRALASIAN JOURNAL OF COMBINATORICS, 88. pp. 52-76. ISSN 1034-4942

Preview

Text 2209.08804v1.pdf Available under License Creative Commons Attribution. Download (849kB) | Preview

Abstract

In an orientation O of the graph G, the edge e is deletable if and only if O − e is strongly connected. For a 3-edge-connected graph G, H¨orsch and Szigeti defined the Frank number as the minimum k for which G admits k orientations such that every edge e of G is deletable in at least one of the k orientations. They conjectured the Frank number is at most 3 for every 3-edge-connected graph G. They proved the Petersen graph has Frank number 3, but this was the only example with this property. We show an infinite class of graphs having Frank number 3. H¨orsch and Szigeti showed every 3-edge-colorable 3-edge-connected graph has Frank number at most 3. It is tempting to consider non- 3-edge-colorable graphs as candidates for having Frank number greater than 2. Snarks are sometimes a good source of finding critical examples or counterexamples. One might suspect various snarks should have Frank number 3. However, we prove several candidate infinite classes of snarks have Frank number 2. As well as the generalized Petersen Graphs GP (2s + 1, s). We formulate numerous conjectures inspired by our experience.

Actions (login required)

Edit Item