Relationship between cycle length, number of chords, and number of induced $P_{4}$ subgraphs of the cycle

Question

I was wondering if there was a known relationship between the length of cycle, the number of chords of the cycle, and the number of induced $P_{4}$ subgraphs of the cycle. Here, I am referring to cycles of length greater than or equal to $5$.

Here $P_{4}$ refers to: Path graph on $4$ vertices (there will be $3$ edges then).

I am primarily interested at the point in which the number of induced $P_{4}$ becomes $0$. I was wondering if there is any closed form expression for this. I mean is there some expression involving the length of the cycle and the number of chords (and probably other quantities) that determines when the number of induced $P_{4}$ is 0

Or is there a closed form expression involving the length of the cycle and the number of chords (and probably other quantities) for the exact number of induced $P_{4}$?

Two things are clear to me: When the number of chords in the cycle increases, the number of induced $P_{4}$ subgraphs decreases. Also when the length of the cycle increases, typically the number of induced $P_{4}$ subgraphs increases.

I did the following examples by hand:

Cycle of length $5$ with $0$ chords: Number of $P_{4}$ induced subgraphs: $5$

Cycle of length $5$ with $1$ chord: Number of $P_{4}$ induced subgraphs: $2$

Cycle of length $5$ with $2$ chords: Number of $P_{4}$ induced subgraphs: $0$

Cycle of length $5$ with $3$ chords: Number of $P_{4}$ induced subgraphs: $0$

Cycle of length $5$ with $4$ chords: Number of $P_{4}$ induced subgraphs: $0$

Cycle of length $5$ with $5$ chords: Number of $P_{4}$ induced subgraphs: $0$

Cycle of length $6$ with $0$ chords: Number of $P_{4}$ induced subgraphs: $6$

Cycle of length $6$ with $1$ chord: Number of $P_{4}$ induced subgraphs: $5$

Cycle of length $6$ with $2$ chords: Number of $P_{4}$ induced subgraphs: $4$

Cycle of length $6$ with $3$ chords: Number of $P_{4}$ induced subgraphs: $3$

Cycle of length $6$ with $4$ chords: Number of $P_{4}$ induced subgraphs: $1$

Cycle of length $6$ with $5$ chords: Number of $P_{4}$ induced subgraphs: $0$

Cycle of length $6$ with $6$ chords: Number of $P_{4}$ induced subgraphs: $0$.

As seen, here for a cycle of length $5$, the number of $P_{4}$ induced subgraphs becomes $0$ when we have a chord of length $2$.

For a cycle of length $6$, the number of $P_{4}$ induced subgraphs becomes $0$ when we have $5$ chords.

Hopefully, I have not made a mistake in the above calculations.

These results would be useful for me for something I'm working on relating to perfect graphs. If there does not exist a result, relating to what I'm asking, can you to relevant research papers or other sources? Thanks.

Answer 1

I agree with

Cycle of length 5 with 0 chords: Number of P4 induced subgraphs: 5 Cycle of length 5 with 1 chord: Number of P4 induced subgraphs: 2

But I'm not sure how to interpret your statement:

Cycle of length 5 with 2 chords: Number of P4 induced subgraphs: 0

There are two ways to have 2 chords in a 5-cycle... crossing chords (in which case the number of $P_4$s is 0, as you wrote) or the two chords could have a common endpoint, making the gem graph, which still has one $P_4$ left in it.

So your question of asking for a closed form for the number of necessary chords needs further clarification: are you asking how many chords are necessary so that no matter how they are added to the cycle, there are no $P_4$s left? Or are you asking for the fewest number of chords one has to add to a cycle (possibly in a clever way) in order to destroy all $P_4$s.

Since $P_4$s are self complementary, you can think about what the complement of the resulting graph is once you reach one of your graphs with zero $P_4$s. The complement will also have no $P_4$s and will be nearly empty of edges... so if we take the interpretation of your question as to ask "What is the fewest number of edges required to add to a cycle strategically in order to destroy all $P_4$s?" we take away edges in the complement until it would be down to a disjoint union of a combination of $K_3+K_1$s (if strategically possible), or $P_3+K_1$s and $2K_2$s (on our chosen partition of $4$-vertex sets).

So the approach in deleting from $\overline{C_n}$ would be to turn every $4$-set of vertices to a triangle ($3$ edges) and an isolated vertex, and when not possible, to reduce a $4$-set down to having $2$ edges (as either a $P_3+K_1$ or a $2K_2$. So on $n=4k$ vertices, you are looking at adjusting (adding in the original, or deleting in the complement) enough edges to leave behind between $2k$ and $3k$ edges.

The complement of $C_n$ has $\left(\frac{n(n-1)}{2}-n\right)$ edges, which is $= \frac{n^2-3n}{2}$ edges, and so you must delete (add) between $\left(\frac{n^2-3n}{2} - \frac{3n}{4}\right)$ and $\left(\frac{n^2-3n}{2} - \frac{n}{2}\right)$ edges, or between $\frac{2n^2-9n}{4}$ and $\frac{2n^2-8n}{4}$ edges.

Checking for $n=5$, this is between $\frac{50-45}{4}$ and $\frac{50-40}{4}$, which is the range [1.25,2.5] = 2, which checks out with your strategic choice of 2 edges.

Check for $n=6$, this is $\frac{72-54}{4}$ and $\frac{72-48}{4}$, which is [4.5,6], the most 'strategic' option would be 5 edges, which corresponds to your hand-computation.

If you computed $C_7$ after your original post, I would think you found a solution of CEIL$\left(\frac{98-63}{4}\right) = 9$ edges.

If you are interested in restricting $P_4$s, you should familiarize yourself with $P_4$-sparse and $P_4$-lite and their related graph classes.

If you are interested in optimal ways of deleting (or adding in the complement) edges from a graph in order to make the graph $P_4$-free, you might want to see this couple of papers which develop and use exact (exponential-time, but FPT) algorithms for deleting graphs until they are $P_4$-free:

• Bounded Search Tree Algorithms for Parameterized Cograph Deletion
• Defining and identifying cograph communities in complex networks