4
$\begingroup$

Let $G(V,E)$ be a graph. A path whose length is equal to the diameter of a graph is called a diametral path. In a cycle graph every vertex has $2$ diametral paths. Now I need to prove that this:

If each $v \in V(G) $ has the same number of diametral paths initiated from it, then $G$ is a regular graph.

$\endgroup$
3
  • 4
    $\begingroup$ Are you sure that this is true? If yes, why? If no, please replace 'I need to prove' to something like 'I want to prove or disprove', if counterexample is not what you need, this may be mentioned too. $\endgroup$ Apr 13, 2016 at 14:18
  • $\begingroup$ Is this true for disconnected graphs? The union of two regular of same order and different degrees? $\endgroup$
    – joro
    Apr 14, 2016 at 5:17
  • $\begingroup$ @L S B. user255259: As I know from the book "Inequalities for Graph Eigenvalues", page 3, the diametral path between two vertices is the shortest path between these vertices with length equal to the diameter of graph. Do you mean this definition or you mean all paths between these two vertices with length equal to diameter? $\endgroup$
    – Shahrooz
    May 7, 2016 at 10:22

3 Answers 3

4
$\begingroup$

The claim is actually false, for both versions of the problem. That is, we may define a diametral path of $G$ as a path with length equal to the diameter of $G$ (I think this is the OP's intent), or as a path with length equal to the diameter with the additional property that it is a shortest path between its ends (this is Shahrooz Janbaz's interpretation).

Here is an infinite family of counterexamples to the second definition (Shahrooz Janbaz has already given a counterexample to the first defintion). Let $G_k$ be the graph obtained from a cycle of length $2k$ by first adding a parallel edge for each edge and then subdividing each edge once. Observe that $G_k$ is not regular (it has vertices of degree $2$ and $4$) and has diameter $2k$. Moreover, if $x$ is a degree $4$ vertex of $G_k$, then there are $2^{k+1}$ diametral paths starting at $x$ (there are $2^k$ in each direction). Similarly, if $y$ is a degree $2$ vertex of $G_k$, there are $2^{k+1}$ diametral paths starting at $y$.

$\endgroup$
5
  • 1
    $\begingroup$ This nice construction also works if one adds $j$ parallel edges for each edge to the cycle, followed by subdividing. In that case there would be $2(j+1)^k$ diametral paths from each degree $2$ or degree $2(j+1)$ vertex. $\endgroup$
    – user85586
    May 21, 2016 at 10:22
  • $\begingroup$ @user85586 good observation. $\endgroup$ May 21, 2016 at 10:50
  • $\begingroup$ @Tony Huynh: we mean a diametral path of G is a path with length equal to the diameter of G. Superb construction thank you. $\endgroup$ May 21, 2016 at 10:55
  • $\begingroup$ @Tony Huynh: Is it possible to count the number of diameteral paths of diameter =2. For example: If for any graph of order n with diameter=1, then number of diametral paths=n(n-1). Similarly, what could be the value of diametral paths for diameter=2. $\endgroup$ May 21, 2016 at 11:03
  • 1
    $\begingroup$ @Tony Huynh: good answer! $\endgroup$
    – Shahrooz
    May 21, 2016 at 12:28
2
$\begingroup$

The answer to your question is $\it{NO}$. The below graph is one example. For each vertex, there is $4$ diametral path, but the graph is not regular.

enter image description here

By my comment in the above, we have another possibility for viewing your problem. I thought that I found a counterexample also for this case, but Tony Huynh noticed me the mistake. I think with this definition, the answer to your question is positive.

$\endgroup$
3
  • $\begingroup$ If I understand correctly, in your definition, a diametral path must be a shortest path (between its ends). So, I don't see how (a) is a counterexample. There are no diametral paths starting from a vertex of the triangle, while there are two starting from each of the degree-1 vertices. $\endgroup$
    – Tony Huynh
    May 17, 2016 at 21:33
  • $\begingroup$ @TonyHuynh: You are right. I will correct it. $\endgroup$
    – Shahrooz
    May 17, 2016 at 21:47
  • $\begingroup$ Actually, the answer turns out to also be false for the other version. See my answer. $\endgroup$
    – Tony Huynh
    May 21, 2016 at 9:53
1
$\begingroup$

Here's another generalization of Tony Huynh's nice construction where every vertex has the same number of diametral paths starting from it and the set of degrees of the vertices in a graph may be large. (The definition of diametral path used here is the one where there is no shorter path between the vertices.) Let's start with a tree of height $h$ where the root has degree $2$ and every vertex in the tree except the root and the leaves has degree $i+3$ where $i$ is the depth of that vertex. The tree has $(h+1)!$ leaves. Take two of such trees and glue their leaves together so that each leaf from the first tree has exactly one edge connecting it to a leaf from the other tree. Such glued trees seem to appear in the contexts of quantum walks. Using the original cycle of length $2k$, replace each edge in the cycle by this glued tree where the roots of the glued tree are replaced by the vertices of the original cycle. It seems that this graph has diameter $(2h+1)k$ and each vertex has $2((h+1)!)^k$ diametral paths starting from it.

$\endgroup$

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.