4
$\begingroup$

G is a graph on n vertices. Each vertex has degree at least 3, and G is not bipartite. Let k be the size of the smallest odd cycle in G. What is the largest k can be, as a function of n?

Vertices of degree 0 and 1 are clearly irrelevant. If we allowed vertices of degree 2 and n was odd, we could have G just be an n-cycle, and get k=n. So these cases kind of break down trivially. But when all degrees are at least 3, we can't have an n-cycle without having lots of chords. If the large cycle is odd and you start adding approximate diameters, you make a good construction until you've gone most of the way around, then you start getting small odd cycles again.

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ The shortest odd cycle in the Cartesian product of $C_k$ and $K_2$ for odd $k$ contains half of the vertices, not sure if that's best possible though. $\endgroup$
    – Florian Lehner
    Commented Apr 10, 2019 at 19:48
  • $\begingroup$ I'm not sure how to prove it either, but that sounds probably tight. For n=4m+2 that gives at least 2m+1=n/2. For other values of n mod 4, I'm now thinking any ways to add a vertex or two to that construction. For n=4m+3, 4m+4 or 4m+5 I see how to still get k≥2m+1 (with modifications not worth describing in a comment) but I'm much less confident those would be tight. $\endgroup$
    – Alex Meiburg
    Commented Apr 10, 2019 at 20:03
  • 1
    $\begingroup$ To add a vertex, just make a copy of an existing one $\endgroup$
    – Ilya Bogdanov
    Commented Apr 10, 2019 at 21:32
  • 1
    $\begingroup$ "In the mathematical area of graph theory, a cage is a regular graph that has as few vertices as possible for its girth. Formally, an $(r,g)$-graph is defined to be a graph in which each vertex has exactly $r$ neighbors, and in which the shortest cycle has length exactly $g$." (quoting Wikipedia). So maybe you want to check out the literature on "cage graphs". $\endgroup$
    – Gerry Myerson
    Commented Apr 10, 2019 at 22:01
  • 1
    $\begingroup$ @GerryMyerson I appreciate the recommendation, but cage graphs also avoid small even cycles. I did search for "odd cages" or something, but without success. $\endgroup$
    – Alex Meiburg
    Commented Apr 10, 2019 at 22:07

1 Answer 1

Reset to default
6
$\begingroup$

I care only about linear term in the answer, relaxing an additive constant. However, for $n=12k+11$ I show the tight answer.

An example I told in a comment was slightly suboptimal. An optimal one is the following. Take a cycle of length $8k+7$, number its vertices from 1 to $8k+7$, and duplicate those with residues $2,3,6,7$ modulo 8. We get $n=12k+11$ vertices, so a shortest odd cycle has length of almost $2n/3$. See below an example for $k=0$.

Assume a shortest odd cycle has length more than $2n/3$. The cycle has no chords (otherwise we shorten the cycle), so each its vertex has a neighbor outside the cycle. Then three vertices have the same outer neighbor, which again leads easily to shortening the cycle (if $n$ is large).

Notice that exactly $2n/3$ is also impossible, as this number is even whenever integer.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I was having a hard time understanding this construction. What is the effect of "duplicating the vertices" on the edges of the graph? A picture or an easy example would help. $\endgroup$
    – Victor Protsak
    Commented Apr 11, 2019 at 5:41
  • $\begingroup$ Each duplicate is connected to all vertices the origin was connected to, as well as to their duplicates. Thus, the degree of each duplicated vertex's neighbor increases. I'll try to make a picture later $\endgroup$
    – Ilya Bogdanov
    Commented Apr 11, 2019 at 5:55
  • $\begingroup$ Thank you, Ilya. So you blow up a set of vertices and A and B are adjacent in the blown up graph iff their images are adjacent in the original graph. $\endgroup$
    – Victor Protsak
    Commented Apr 11, 2019 at 6:13
  • $\begingroup$ Right! I've added a picture. $\endgroup$
    – Ilya Bogdanov
    Commented Apr 11, 2019 at 6:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .