Seminár z teórie grafov - Ján Mazák (23.3.2017)

vo štvrtok 23.3.2017 o 9:50 hod. v miestnosti M/213

---

Prednášajúci: Ján Mazák

Názov: Circumference deficit of cubic graphs

Termín: 23.3.2017, 9:50 hod., M/213

Abstrakt:
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)|.

 

 

---