3
$\begingroup$

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?

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

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
3
  • $\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$ 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$ Sep 14, 2013 at 18:46
  • $\begingroup$ But we need $\leq 2m+1$! $\endgroup$ Sep 15, 2013 at 7:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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