0

Given a simple directed graph G=(V,E) an induced cycle is a cycle where no two vertices of the cycle have an edge that is not in the cycle.

(Chordless cycles are induced cycles with at lease 4 vertices).

My question is what is the maximum number of induced cycle a simple directed graph can have?

I have looked around the web quite a bit. However I was not able to find an answer to this specific question.

  • 1
    What is the definition of "circuit" in this context? If it's the same as the graph G, it seems impossible for an induced circuit to exist by definition. If a circuit is any subset of the vertices of G, it seems like the only induced circuit is the trivial one that equals G exactly. So there's something missing without which the problem doesn't make any sense. – Ixrec May 16 '16 at 20:05
  • @lxrec A circuit is just a directed cycle. More formally a circuit is a path {v_1,v_2,...v_n} where {v_i, v_i+1} is an edge in G for all i, and {v_n, v_1} is also an edge in G. An induced circuit is where no other {v_i, v_j} in the path is an edge in G. Maybe I should clarify more in the question. – stardust May 16 '16 at 20:15
  • Do you want the "maximum" as a multiple of V or a multiple of E or some combination of the two? Since the literal maximum is obviously "infinitely many". – Ixrec May 16 '16 at 20:33
  • @lxrec It is not infinitely many. The graph is of course finite. For finite V and E there is always a finite number of induced cycles. Even simple cycles (where we don't have the restriction of edges not lying in the cycle) the upper limit is given here researchgate.net/publication/…. (preview but you can see the limit there). Since Induced cycles are subsets of simple cycles there is less of them. – stardust May 16 '16 at 20:43
  • I meant in the general case if you're asking about all possible graphs. Again, lots of ambiguity in your question. But I think I've worked out what the answer is for my best guess interpretation of what you're trying to ask. – Ixrec May 16 '16 at 20:49
1

If the graph is directed, that implies that no cycle can contain the same edge twice.

If the graph is simple (assuming you really meant a simple graph), that implies that there are no "loop" edges starting and ending at the same vertex, and that any pair of distinct vertices has at most one edge between them.

From those assumptions, we can easily show that any circuit (induced or otherwise) must contain at least three vertices and at least three edges. A circuit with one vertex would have to use a loop edge; a circuit with two vertices would have to reuse a single edge or have two edges between the same two vertices; etc.

Now, given any two distinct circuits (induced or otherwise), those two circuits cannot share all three vertices. If they did, they would either be the same circuit, or there would again be two different edges between the same pair of vertices. By essentially the same logic, any two distinct circuits cannot share more than one edge.

The result that distinct circuits share at most two vertices and at most one edge implies that for any graph G(V,E), there cannot be more than V-2 circuits, and there cannot be any more than (E-1)/2 circuits.

Now I can prove this upper bound is not only a bound but also a maximum by presenting a simple example that reaches it. Let G contain vertices A and B, with edge X from A to B. There are currently 0 cycles, 2 vertices and 1 edge. Now add a vertex C1, plus an edge Y1 from B to C1 and another edge Z1 from C1 to A. Now we have 1 cycle (which is obviously induced), 3 vertices and 3 edges. Similarly, add vertex C2 and edges Y2 and Z2 so that we have 2 induced cycles, 4 vertices and 5 edges. Continue the pattern, and by induction, when we add CN, YN and ZN, we'll have N induced cycles, 2+N vertices and 1+2N edges. That means N=V-2 and N=(E-1)/2, which was our theoretical upper bound.

Thus, the maximum number of induced circuits/cycles in a graph G(V,E) is the minimum of V-2 and (E-1)/2.

  • 1
    I still have no idea if I guessed the correct interpretation of your question, but this was fun to work out and I'm pleasantly surprised I found a proof for something non-obvious so I'll call it a win either way. – Ixrec May 16 '16 at 21:15

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.