I'm working on simulating a network architecture. I'm representing every node and their connections as a connected graph with no directional edges. I need some help with my reasoning.

Every node in network is connected to exactly 3 others. Is it possible for me to prove that every two nodes have a path of length O(n/3) between them? I can show people that the way I setup the network guarantees some existence of relatively fast routes. The n is much more than 3

Thank you

  • $\begingroup$ I undid your edit because it changed your question to something completely different after it had already been answered, so my answer no longer made sense. Please post your new question as a new question. $\endgroup$ – David Richerby Mar 27 '17 at 7:35

$O(n/3)$ doesn't mean what you think it means: in particular, $O(n/3)$ denotes exactly the same class of functions as $O(n)$. However, it's not true that the longest distance between two vertices in a $3$-regular graph is roughly $n/3$. Consider the graph

o---o       o       o             o       o---o
|\ / \     /|\     /|\           /|\     / \ /|
| X   o---o | o---o | o-- ... --o | o---o   X |
|/ \ /     \|/     \|/           \|/     \ / \|
o---o       o       o             o       o---o

(where the Xs denote two crossing edges). The distance from the top-left vertex to the top-right vertex is approximately $3n/4$.

  • $\begingroup$ Thank you for picture, it's very informative. I see the error of the questioning now. Does same reasoning still hold if 3 is 3 billion? If it's many many magnitudes greater than n? $\endgroup$ – ojil Mar 27 '17 at 0:25
  • $\begingroup$ $n$ is usually the number of vertices in the graph. Do you mean something else by it? Because, if there are $n$ vertices, no vertex can have more than $n-1$ neighbours, and it certainly can't have a number of neighbours that's "many magnitudes greater." I'm not sure what the answer is for values between $3$ and $n-1$. Try Googling for something like "diameter of bounded degree graphs". (If I remember, I'll have a look in the morning but I need to go to bed, now.) $\endgroup$ – David Richerby Mar 27 '17 at 0:30
  • $\begingroup$ Thank you for the help and resources, error in the phrasing. I meant to inquire for n is 3 billion and is the many many magnitudes greater than 3 edges between all nodes. I will Google. $\endgroup$ – ojil Mar 27 '17 at 0:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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