doubt over an equation

133 Views Asked by At

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

1

There are 1 best solutions below

0
On BEST ANSWER

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$).