5
$\begingroup$

Let $k$ be a positive integer and $G=(V,E)$ be a $2$-connected simple graph.Suppose $v\in V(G)$ satisfy:

$(1)$there exists at least one vertex $u\in V(G)\backslash\{v\}$ such that $u$ is not adjacent with $v$;

$(2)$for any $u\in V(G)\backslash\{v\}$ such that $u$ is not adjacent with $v$,there is a $u$-$v$ path in $G$ which has an odd length $\geq2k+1$.

I want to ask is it ture that there must exists a odd cycle in $G$ whose length$\geq2k+1$.

Improve this question
$\endgroup$
4
  • $\begingroup$ What about a complete bipartite graph? $\endgroup$
    – Brendan McKay
    Commented Oct 15, 2013 at 4:02
  • $\begingroup$ Sorry,I forgot "odd"! $\endgroup$
    – user40096
    Commented Oct 15, 2013 at 6:12
  • $\begingroup$ An odd path means a path of odd length? $\endgroup$
    – Gerry Myerson
    Commented Oct 15, 2013 at 10:13
  • $\begingroup$ Yes,it is my meaning. $\endgroup$
    – user40096
    Commented Oct 15, 2013 at 12:05

1 Answer 1

Reset to default
5
+50
$\begingroup$

False. As we want a counterexample, we naturally start with the Petersen graph, P. Note that for any vertex v of P and non-adjacent edge uw of P there is a Hamiltonian path from v to w that does not use the uw edge. On the other hand, there is no Hamiltonian cycle in P.

Our graph G will have 10t+15 vertices (where t is some large number) and is obtained from P by subdividing each edge with a vertex and replacing each original vertex by t vertices, connected to each other and to the subdividing vertices which the original vertex was connected to. Let v be a vertex that was not obtained by subdividing an edge and let 2k+1=9t+16 (or +17, whichever is odd). Using the above mentioned properties of P, it is easy to see that G satisfies the requirements if t is big enough.

This graph is even 3-connected and can be generalized to give even stronger counterexamples.

Note that my original construction used t=2, which is not sufficient for the above reasoning, as was noted in the comment by Dani.

Improve this answer
$\endgroup$
9
  • 2
    $\begingroup$ I fount a 29 long cycle in your graph. Since it is too big to draw it, i will describe how to find it. There is a 9 long cycle in the Petersen graph which naturally yields a 27 long cycle in your graph. Now we can use that by subdividing edges and replacing vertices you created a lot of triangles. And by the help of two such triangles we can expand it to a cycle of length 29. $\endgroup$
    – Daniel Soltész
    Commented Nov 2, 2013 at 12:25
  • $\begingroup$ Yeah, you are right, I've missed that! Nevertheless, I think the main idea is correct, so let me fix my construction accordingly. $\endgroup$
    – domotorp
    Commented Nov 2, 2013 at 16:48
  • $\begingroup$ I actually really like the idea of your construction! But i just happen to have another question. Now you have t-clicques instead of original vertices. And in one such t-clicque, there is the vertex $v$. But there are vertices in the closest t-clicques which are not adjacent to $v$. How do you ensure that there is a path of length greater than $9t+15$ from $v$ to them? This length essentially means that we have to at least touch every t-clicque, and in your construction we can use every edge only once, so without a Hamiltonian cycle i'm not sure that we can achieve this. $\endgroup$
    – Daniel Soltész
    Commented Nov 2, 2013 at 17:40
  • 1
    $\begingroup$ If u and v are adjacent vertices of the Petersen-graph, then there is a walk that starts at u, ends at v and uses every vertex once, except for u, which is used twice. In G, this can be realized by a path, as we can take different vertices from the blown-up of u. Does this answer your question? $\endgroup$
    – domotorp
    Commented Nov 2, 2013 at 18:51
  • $\begingroup$ Yes it does! Actualy this means that the property that 'there is a Hamiltonian path between $v$ and any vertex not adjacent to $v$' is preserved when $t$ is large enough (greater than 3 is sufficient). This might help others who would like to verify your counterexample! $\endgroup$
    – Daniel Soltész
    Commented Nov 2, 2013 at 19:05

You must log in to answer this question.

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