Sign up ×

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.

enter image description here

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.

share|cite|improve this question
I must be missing something. If I take $G=K_n$, then unless $|T|\geq n-3$, you will not intersect all $P_4$s. –  R B Mar 18 '14 at 0:02
@RB Sorry for the misunderstanding. We consider induced P4. Therefore, there is no induced P4 in a complete graph. –  Peng Zhang Mar 18 '14 at 0:03
This makes more sense :). As I assume you've noticed, a $n/4$ lower bound is easy - $G=(V_1\cup V_2\cup V_3\cup V_4 , V_1\times V_2\cup V_2\times V_3\cup V_3\times V_4)$ for $|V_1|=|V_2|=|V_3|=|V_4|=\frac{n}{4}$. Do you have an example of a graph for which any $|T|<\frac{n}{3}$ is not a valid transversal? –  R B Mar 18 '14 at 0:23
@RB Thank you very much. I think I disproved it by extending your idea. Could you help me check whether the example in the answer is valid? –  Peng Zhang Mar 18 '14 at 0:44

3 Answers 3

up vote 2 down vote accepted

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 (?)


share|cite|improve this answer
the ratio is indeed 1, see my answer. –  R B Mar 18 '14 at 7:02

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$.

share|cite|improve this answer
This is not the standard usage of cartesian product for graphs -- can you give a source for this "full cartesian product" ? If this construction is the same as the one I gave, "graph substitution" is more appropriate. Graph substitution is not commutative, while the cartesian product is (when dealing with unlabeled graphs.) –  Jim Nastos Mar 18 '14 at 7:53
@JimNastos I agree. It is not the standard definition of cartesian product of graphs. If it is, $P_4^2 = P_4^1 \square P_4^1$ would be a grid of 4*4 = 16 nodes. –  Peng Zhang Mar 18 '14 at 8:16
I am sorry for the mistake made to edit the answer. $P_4^1 \square P_4^1$ has a minimal $P_4$-transversal of 4 vertices. Therefore, I think you may mean the same construction as the one in Jim's answer. –  Peng Zhang Mar 18 '14 at 8:39
@JimNastos, I'm not sure if this is the technical term, so thanks for the correction. I think of $P_4^k$ as a $k$-dimentional grid (over $\{1,..,4\}^k$), where $(x,x')\in P_4^k$ if $|x-x'|_\infty=1$. –  R B Mar 18 '14 at 8:40
@RB well, yes, that is the cartesian product, but you said the example in the question is $P^2_4$, but that example is not a cartesian product. A cartesian product of two paths will be triangle-free, but the example graph has many triangles. –  Jim Nastos Mar 18 '14 at 8:51

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.

enter image description here

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?

share|cite|improve this answer
Its not minimal in the case that we can get the same ratio if you use each H simply as a P4. Then your G will have 16 vertices and a transversal requires 7 of those 16. –  Jim Nastos Mar 18 '14 at 1:02
@JimNastos Thanks a lot. So the ratio can be pushed up to 7/16. Maybe the upperbound of the ratio is 1/2? –  Peng Zhang Mar 18 '14 at 1:06
I don't think I changed your ratio, since your example of 32 vertices used 14 vertices in the transversal... no? –  Jim Nastos Mar 18 '14 at 1:12
@JimNastos No, 7/16=14/32. But your made it simpler. –  Peng Zhang Mar 18 '14 at 1:17

Your Answer


