Longest Loop in Graph

280 Views Asked by At

Please consider the following graph:

enter image description here

Is there a formal definition for the longest nonrepeating sequence of vertices which form a loop in a graph? (A, G, B, C, D, E, F)

And how about the longest loop without shortcuts? (A, B, C, D)

The closest I'm aware of is the Graph Diameter, but that's obviously very different.

1

There are 1 best solutions below

1
On BEST ANSWER

What you call "loop" is more commonly known as a cycle, and there doesn't seem to be any common term other than "longest cycle".

Your "loop without shortcuts" appears to be a chordless cycle. Again, I don't think there's a commonly used nicer term than "longest chordless cycle".