Skip to main content
1 of 2

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

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.