The length of any longest cycle in an arbitrary graph $G$ is called the circumfrence of $G$.

While the length of any shortest cycle in an arbitrary graph $G$ is called the girth of $G$.

With that said is there a special name/notation for the length of any longest path in a graph $G$?

Also while on the topic are there any particularly special instances when the diameter of a graph is equal to the length of its longest path? For example when $G$ is a tree, I know the diameter is equal to the longest path. Though obviously the two in general are different from one and another. What about other special cases? Are there any other interesting types of graphs where the diameter is equal to the length of the longest path?

  • 5
    $\begingroup$ I expect there isn't a one-word term for "longest path", otherwise the longest path problem would be called the <one-word term> problem. $\endgroup$ – Rahul Mar 5 '18 at 15:21

No there isn’t a special term for a longest path in a graph. You can refer to it as a longest path or a path of maximum length or a maximal path etc...

  • $\begingroup$ What about "depth" or "perimeter" or something? I see a lot of terms/stuff in graph theory sorta spins off stuff in topology, maybe there is a topological word? Also how do you write the other graph invarients. I know the diameter of a graph $G$ is written $\text{diam}(G)$, how about girth/circumference of $G$? Is that $\text{grth}(G)$ and $\text{circ}(G)$? Or something else? $\endgroup$ – user3865391 Mar 5 '18 at 17:02
  • $\begingroup$ Again there is no standard way of writing or referencing these invariants. It generally depends upon the text you are reading. Specifically I have seen $\operatorname{diam}(G)$ for diameter and $\operatorname{rad}(G)$ for radius, but both of those are relative to the metric being used to measure the distances in a graph. As long as you pick something descriptive and define it carefully and clearly, you’ll be fine. $\endgroup$ – Laars Helenius Mar 7 '18 at 11:45

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.