# On cycles in self-centered graphs

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?

• Let $m>1$ otherwise a single edge provides a counterexample. Sep 13, 2013 at 18:05
• No, if we all agree that edge is a cycle of lenght $2$ :) Sep 13, 2013 at 18:14

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.
• Thanks! My original question is obviously stupid. But what one could say if we replace "$C_{2m}$" by "$C_{2m}$ or $C_{2m+1}$"? Sep 13, 2013 at 16:41
• 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$. Sep 14, 2013 at 18:46
• But we need $\leq 2m+1$! Sep 15, 2013 at 7:26