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?
MathOverflow is a question and answer site for professional mathematicians. It only takes a minute to sign up.
Sign up to join this communityLet $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?
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.