Seminar of Graph Theory - Ján Mazák (23.3.2017)

Thursday 22.3.2017 at 9:50, Lecture room M/213

21. 03. 2017 10.28 hod.
By: Martin Škoviera

Ján Mazák:
Circumference deficit of cubic graphs

Abstract:
The circumference deficit of a graph G is the difference between order and circumference of G. The circumference ratio of a graph G is the ratio of circumference to order of G. We observe that a snark with large resistance has large circumference deficit. By applying several recent results on resistance of snarks, we are able to construct infinite families of cyclically k-connected cubic graphs with circumference ratio less than 1 for each k between 2 and 6. We extend these results to snarks of large girth, solving a problem proposed by Markstrom.

In addition, we construct a non-trivial snark of order 8k and circumference 7k+2 for each integer k above 2. This result contrasts a corollary of the dominating cycle conjecture saying that each non-trivial snark G contains a cycle of length at least 0.75|V(G)|.