Skip to main content
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user

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

Source Link

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.