Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am having doubt over an equation. That is my calculation. Can anybody check and find the error, if any. Specially in the last line. I am confused. Thanks a lot.

NOTE : please check only last two equations. Here I am asking whether we can write $min\{d(g,g'),d(h,h')\}$ as $min\{ecc(g),ecc(h)\}$ where $d(g,g')$ runs over every vertex $g \in V(G)$. We know that max{d(g,g'),d(h,h')} can be written as $max\{ecc(g),ecc(h)\}$.

Am I right in writing $min\{d(g,g'),d(h,h')\}$ as $min\{ecc(g),ecc(h)\}$. If I am wrong please help me there. If any other details needed, please mention that. I will do that too. We took vertex as $(g,h)$ because its a vertex of product graph and for such graphs vertex set is the cartesian product of $V(G)$ and $(VH)$.

enter image description here

share|cite|improve this question
Please define the terms and add more details about the part that's confusing you. I think this will improve your chances of getting a useful answer. – Daniel R Aug 9 '13 at 7:27
@DanielR... sorry for late reply..... ecc is the eccentricity...d(g,h) denotes the distanc between vertices g and h. ecc of a vertex v is the distance of a vertex farthest from v. thid might help u – monalisa Aug 9 '13 at 8:36
In the first line $(g',h')$ must be in the vertex set of the product graph, not in $V(G)$. Which graph product are you using? – Brian M. Scott Aug 9 '13 at 14:28
@BrianM.Scott... oh .... silly mistake. its co-normal product – monalisa Aug 9 '13 at 18:29
up vote 2 down vote accepted

There is something, I guess. As exhibited here, no distance in $G$ can be $>2$. You seem to have a different idea thatn that in the step from line 1 to line 2. But the step from line 2 to line 3 is correct: As the $\max$ is taken over all possible choices of $(g',h')$ we may pick $g'$ and $h'$ so that they witness the eccentricity of $g$ and $h$ respectively. Maybe your confudion comes from the notation. The minimum is not taken over all choices of $g'$ and $h'$, it is simply the minimum of th etwo-element set $\{d(g,g'), d(h,h')\}$. A less ambiguous (but not necessarily more readable) notation for the expression in line 2 might have been $$ \max\Bigl\{2,\max\bigl\{\,\min\{d(g,g'),d(h,h')\}\bigm| g'\in V(G), h'\in V(H)\,\bigr\}\Bigr\}.$$

By the results in the question linked above, the eccentricity of $(g,h)$ in the co-normal product of connected graphs with more than one vertex each cannot exceed $2$. If $\operatorname{ecc}(g)>1$ and $d(g,g')>1$, say, then $(g',h)\not\sim (g,h)$, hence $\operatorname{ecc}(g,h)\ge2$ and by the above remrark $=2$. The same holds if $\operatorname{ecc}(h)>1$. Only if $\operatorname{ecc}(g)=\operatorname{ecc}(h)=1$ we have $(g,h)\sim(g',h')$ for all $(g',h')$, including the cases where one of $g'=g$ or $h'=h$ holds. In all these cases we verify that $$ \operatorname{ecc}(g,h)=\min\Bigl\{2,\max\bigl\{\operatorname{ecc}(g),\operatorname{ecc}(h)\bigr\}\Bigr\}.$$ If one of the factors is the one-point graph, note that the conormal product is just the other factor and hence the eccentricity is just the same as in that graph (and can exceed $2$).

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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