Let $G$ be (connected) self-centered graph, i.e. $r(G)=d(G)=m<\infty$.
My question is following
Does $G$ always contains $C_{2m}$ or $C_{2m+1}$ as a subgraph?
$\begingroup$
$\endgroup$
2
asked Sep 13, 2013 at 13:38
-
$\begingroup$ Let $m>1$ otherwise a single edge provides a counterexample. $\endgroup$– Daniel SoltészCommented Sep 13, 2013 at 18:05
-
$\begingroup$ No, if we all agree that edge is a cycle of lenght $2$ :) $\endgroup$– Sergiy KozerenkoCommented Sep 13, 2013 at 18:14
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
No. $C_{2k+1}$ is self-centered with $r(G)=d(G)=k$, but obviously does not contain $C_{2k}$ as a subgraph.
With regards to the revised question, here is a proof that $G$ contains a cycle of length at least $2m$.
Proof. Let $G$ be a connected graph with $r(G)=d(G)=m>1$. I first claim that $G$ is 2-connected. To see this, suppose that $G$ had two subgraphs $G_1$ and $G_2$ such that
$G_1 \cup G_2=G$ and $V(G_1) \cap V(G_2)=\{v\}$. Since $r(G)=d(G)=m$, there is a vertex
$y$ such that $d(v,y)=m$. Suppose $y \in V(G_1)$. Letting $z$ be any neighbour of $x$ in $G_2$, we have that $d(y,z)>m$, which contradicts $d(G)=m$.
Now let $a$ and $b$ be two vertices such that $d(a,b)=m$. By 2-connectivity, there is a cycle $C$ that contains both $a$ and $b$. We are done since $|C| \geq 2m$, else $d(x,y) <m$.
I think if you choose $C$ as short as possible, you can do some re-routing to show that in fact $|C| \leq 2m+1$, but I haven't thought about this too much.
answered Sep 13, 2013 at 15:07
-
$\begingroup$ Thanks! My original question is obviously stupid. But what one could say if we replace "$C_{2m}$" by "$C_{2m}$ or $C_{2m+1}$"? $\endgroup$ Commented Sep 13, 2013 at 16:41
-
$\begingroup$ Certainly if you choose $C$ to be as short as possible, it has length at most $3m+1$, since otherwise the center vertices on the return path would be too far away from $a$ and $b$. $\endgroup$ Commented Sep 14, 2013 at 18:46
-
$\begingroup$ But we need $\leq 2m+1$! $\endgroup$ Commented Sep 15, 2013 at 7:26