2
$\begingroup$

Are there specific terms or adjectives in graph theory to name these two situations?

  • Two vertices are non-adjacent (disjoint? I have seen that the term "disjoint" is rather used for paths with non-common vertices or edges).
  • Two connected non-adjacent vertices (the shortest path or paths connecting them have a lenght $> 1$).
Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ For the first situation, I've only seen "non-adjacent", "nonadjacent", "non-neighbo[u]r[ing]". Larger groups of vertices, no pair of which are adjacent, are an "independent set" or "stable set". Some papers define "$u$ misses $v$" to mean $u$ is not adjacent to $v$. $\endgroup$ – j_random_hacker Aug 11 '19 at 15:01
2
$\begingroup$

You've exactly described the first situation, i.e. we indeed say that $u$ and $v$ are non-adjacent. For the second we do the same, but we want to also specify they are in the same component of $G$ which contains them if $G$ is not connected.

These are already simple and well-understood descriptions and there's nothing "more standard". However, you are also free to use your own definitions in your actual use case if it's worth it.

Improve this answer
$\endgroup$

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.