An approach to the girth problem in cubic graphs

arXiv2206.14638MaRDI QIDQ6403522FDOQ6403522

Nathan Linial, Aya Bernstine

Publication date: 29 June 2022

Abstract: We offer a new, gradual approach to the largest girth problem for cubic graphs. It is easily observed that the largest possible girth of all $n$-vertex cubic graphs is attained by a $2$-connected graph $G=(V,E)$. By Petersen's graph theorem, $E$ is the disjoint union of a $2$-factor and a perfect matching $M$. We refer to the edges of $M$ as chords and classify the cycles in $G$ by their number of chords. We define $gamm{a}_k(n)$ to be the largest integer $g$ such that every cubic $n$-vertex graph with a given perfect matching $M$ has a cycle of length at most $g$ with at most $k$ chords. Here we determine this function up to small additive constant for $k=1,2$ and up to a small multiplicative constant for larger $k$.

This page was built for publication: An approach to the girth problem in cubic graphs

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