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$.

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

1 Answer 1

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.

$\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$ 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
    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$ 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
    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$ Nov 2, 2013 at 19:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.