Improved bounds for the shortness coefficient of cyclically 4-edge connected cubic graphs and snarks

Publication date: 16 September 2013

Abstract: We present a construction which shows that there is an infinite set of cyclically 4-edge connected cubic graphs on

n

vertices with no cycle longer than

c_{4} n

for

c_{4} = f r a c 1213

, and at the same time prove that a certain natural family of cubic graphs cannot be used to lower the shortness coefficient

c_{4}

to 0. The graphs we construct are snarks so we get the same upper bound for the shortness coefficient of snarks, and we prove that the constructed graphs have an oddness growing linearly with the number of vertices.

This page was built for publication: Improved bounds for the shortness coefficient of cyclically 4-edge connected cubic graphs and snarks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6244825)