Saturday 10 August 2013

a doubt in finding distance in graph theory

a doubt in finding distance in graph theory

I was studying about a product graph which is defined as :
..
I am taking $G_1$ and $G_2$ as connected graphs.
I found that for any 2 vertices $(g,h),(g',g')$,
$(d(g,h),(g',h')$ = 1 if $g \sim g'$ or $h\sim h'$
$(d(g,h),(g',h')$ = 2 if $ g=g' ~or ~h=h'$
$(d(g,h),(g',h')$ = min{d(g,g'),d(h,h')}, otherwise.
Here d denotes the distance between vertices and ~ means adjacency. Am I
right in finding the above result? Is there any flaw. Please rectify if I
am wrong.
Heartily thanks.
NOTE: 1st clause in the the formula directly follows from definition. In
2nd clause i took g=g'. the the vertices are like (g,h) and (g,h'). There
must exist a vertex b such that g is adjacent to b. thus we get a path of
length 2: (g,h)(b,c)(g,h'), where c is any vertex in $G_2$. thus distance
is 2 in this case. I am doubtful about 3rd clause.

No comments:

Post a Comment