On the size of P4-transversals of graphs

Question

A subset $T$ of vertices of a graph $G$ is called a $P_4$-transversal if $T$ intersects every $P_4$ of $G$. In the context of this question, we consider $P_4$ as an induced path on 4 vertices.

Conjecture : Given a graph $G$ of $n$ vertices, the minimal $P_4$-transversal of G is of at most $\frac{n}{2}$ vertices.

We consider gneral simple graphs here. However, any results of subclasses of simple graphs are welcome.

Thoughts: $P_4$-transversal can be seen as a special case of hitting set of sets of size 4. However, for general hitting set of 4-sets (i.e., 4-uniform hypergraph) on $n$ vertices, the minimum hitting set can be as large as $n-3$.

The original version of this question guessed the upperbound of the size of $P_4$-transversal as $\frac{n}{3}$. Thanks to the comments from R B and Jim Nastos, we have an example on 16 vertices and whose minimal transverval has 7 vertices.

Introduction and why I am interested in $P_4$-transversal of graphs.

Study of $P_4$-transversal is a part of study of $P_4$-structures of graphs, which plays an important role in the "Strong Perfect Graph Theorem". $P_4$-transversal of perfect graphs and chordal graphs were studied in perfect graph and chordal graph.

$P_4$ is a path of 4 vertices. A $P4$-free graphs is called a cograph, which is the minimal family of graphs generated from $K_1$ and complementation and disjoint union. Therefore, $P_4$ structures seems to be an interesting and important property of graphs.

Answer 1

Let H be any graph on N vertices and requires T vertices in a P4-transversal (so its ratio is T/N). Construct G like in the previous examples: G is a P4 but substitute an H in for each vertex. Then the total number of vertices of G is n = 4N and the transversal size is N + 3T.

This gives a ratio of (N+3T)/4N = (1/4) + (3/4)T/N

So, the last example I gave in the comment of Peng Zhang's answer used H = $P_4$ with T/N = 1/4 and the ratio was 1/4 + 3/16 = 7/16.

Now use that 7/16 graph in for H and construct G. This uses 64 vertices, and the transversal size is 16 + 3(7) = 37. We get a ratio of (1/4) + (3/4)(7/16) = 16/64 + 21/64 = 37/64 which is already over 50%.

This seems correct to me (in that I don't see what is wrong with it) but it is troublesome, because repeating this process will get to a fixed point x = (1/4) + (3/4)x , which is x=1.0 (?)

Thoughts...?

Answer 2

Here's an alternative analysis.

Denote by $P_4^1$ a simple path of size 4, and $P_4^k=P_4^{k-1} \square P_4^1$ (i.e. full Cartesian product).

The example in your question is $P_4^2$, and it's minimal transversal is indeed $7/16$.

Taking $P_4^3$, we already get a minimal transvesal of size $37$, which is $0.578125n$.

In general, the minimal transersal for $P_4^k$ is $T(k)=3T(k-1)+4^{k-1}=..=4^k-3^k$.

The ratio $\frac{T(k)}{4^k}$ trivially converges to 1 as $k\to \infty$.

Definition of cartesian product from textbook "Graph Theory" by J.A. Bondy and U.S.R. Murty. The cartesian product of simple graphs $G$ and $H$ is the graph $G \square H$ whose vertex set is $V(G)\times V(H)$ and whose edge set is the set of all pairs $(u_1, v_1)(u_2, v_2)$ such that either $u_1u_2 \in E(G)$ and $v_1=v_2$, or $v_1v_2 \in E(H)$ and $u_1=u_2$.

Answer 3

Following the idea of user R B pointed out in the comment, I think the following example may have disproved the conjecture in the question.

Let $H$ be the following graph on 8 vertices. It is clear that, the minimal $P_4$-transversal of $H$ has 2 vertices. For example, the two red vertices.

Now we construct a graph $G$ of 32 vertices. First, make 4 disjoint copies of $H$, $H_1$,$H_2$,$H_3$,$H_4$. Then, let $G$ be the union of $H_1$ join $H_2$, $H_2$ join $H_3$ and $H_3$ join $H_4$.

Is the minimal $P_4$-transversal of $G$ has 14 vertices. We can choose $H_1$ and 6 vertices, 2 from each $H_2$, $H_3$ and $H_4$, as a $P_4$-transversal. Is this a minimal one? Does there exist another one of at most $11 = \lceil \frac{32}{3} \rceil$ vertices?