Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

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

enter image description here

enter image description here

I was doing tensor product of graphs. We know that to find a walk between every two vertices x and y of any arbitrary length l in G, the graph must contain an odd cycle. I am stuck here. Is it possible to find l that is common for every pair of vertices. I mean to find an l such that every pair of vertices have a walk of length l between them. Or any particular type of graph where this is possible. Any kind of help or suggestion will be helpful, Thanks a lot.

Can we find such n that satisfies the Prop 5.7 for every pair of vertices in G and H? Actually i want the max{d(a,b),(c,d)} where a and c are in G, b and d are in H

Also Its related to my last post on thi page. I hope the following link will help

Is it possible to have a walk between every two vertices of any arbitrary length in a graph?

share|cite|improve this question
What do you mean by:"We know that to find a walk between every two vertices x and y of any arbitrary length $l$ in $G$, the graph must contain an odd cycle". If $l=1$ it's not sufficient, is it? – wece Jul 29 '13 at 18:29
up vote 1 down vote accepted

In the previous question you link to in this question, the answer by Doug Stones shows, assuming the graph is not bipartite, why for each pair $(x,y)$ of vertices there is a positive integer $L$ such that, for each length $l\ge L$, there is a path from $x$ to $y$ of that length $l$.

Since a graph with $n$ vertices has less than $n^2$ pairs $(x,y)$ of vertices for which a path is sought, you can use the above result and define $L^*$ to be the maximum value of $L(x,y)$ for all the pairs $(x,y)$ of vertices, where by $L(x,y)$ is meant some choice of $L$ for vertices $x,y$ as in the result above. Then if you choose any particular $l \ge L^*$ there will be (uniformly in the choice of $x,y$) a path of that length $l$ from $x$ to $y$.

share|cite|improve this answer
you mean to say that after taking maximum of all L we will get a particular L'. and for any two vertices x and y, we will get a walk of length L'. x and y arbitrary. Am I right ?? – monalisa Jul 30 '13 at 2:06
@monalisa That is correct, if $L'$ is the max of all the $L$, one $L$ for each pair $(x,y)$ of vertices in the graph. I just called that max by the symbol $L^*$ instead of $L'$. Also the same thing holds if we look at any fixed length $L''\ge L'.$ – coffeemath Jul 30 '13 at 2:28

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.