0
$\begingroup$

Graphs can contain circuits, i.e. paths which start and end at the same node. Most circuits are 'non-flat', like this:

Graph with circuit

I'm trying to find a term that describes a particular type of circuit. You might describe it as 'flat', 'zero-volume' or 'doubling-back'.

The circuit visits some nodes in the following order: $[n_{1}, n_{2}, \dots, n_{x-1}, n_{x}, n_{x-1}, \dots, n_{2}, n{1}]$.

Here's an illustration of the same concept:

Graph with 'flat' circuit

$\endgroup$
1
  • $\begingroup$ A simple graph has undirected edges, and only a single edge between any two vertices. So, among simple graphs, any path could be deemed a 'flat' circuit, should you so choose. A directed graph similarly tends to have a single edge between any two vertices. But, that edge may be unidirectional or bidirectional. If every edge is bidirectional, then every path yields a 'flat' circuit. So, it is not entirely clear what you are looking for. Depending on the context, there could be more than one name for what you want. $\endgroup$ Apr 22, 2020 at 12:22

1 Answer 1

0
$\begingroup$

The terminology I see most commonly used is as follows: A closed walk is a sequence of adjacent vertices which starts and ends at the same vertex (your second example is a closed walk). A cycle is a closed walk with no repeated edges or vertices, except the start and end vertex (your first example is a cycle).

So your 'flat circuits' would be referred to as 'closed walks with no induced cycle'.

$\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.