<p>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.</p>

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

<p>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.</p>

<p>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%.</p>

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

<p>Thoughts...? </p>

CC BY-SA 3.0
2014-03-18T07:02:57.053Z
the ratio is indeed 1, see my answer.
R B
CC BY-SA 3.0
2014-03-18T01:40:17.157Z
2014-03-18T01:40:17.157Z
JimN
<p>Here's an alternative analysis.</p>

<p>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).</p>

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

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

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

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

<p>Definition of cartesian product from textbook "Graph Theory" by J.A. Bondy and U.S.R. Murty.
The <em>cartesian product</em> 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$.</p>

CC BY-SA 3.0
2014-03-18T07:53:37.023Z
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.)
JimN
CC BY-SA 3.0
2014-03-18T08:16:27.593Z
@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
CC BY-SA 3.0
2014-03-18T08:39:30.210Z
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
CC BY-SA 3.0
2014-03-18T08:40:33.973Z
@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
CC BY-SA 3.0
2014-03-18T08:51:44.500Z
@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.
JimN
CC BY-SA 3.0
2014-03-18T08:59:30.197Z
@RB Oh, wait, I think if your norm was $|.|_1$, then we'd be talking about the standard graph cartesian product... but your interpretation of using $|.|_\infty$ is different and might coincide with the original construction... I'm not sure
JimN
CC BY-SA 3.0
2014-03-18T20:13:08.813Z
@RB After sleeping on it, yes, your measure of using $|.|\infty$ is identical to the graph substitution construction. But I've never seen that referred to as a cartesian product on graphs.
JimN
CC BY-SA 3.0
2014-03-18T07:00:28.420Z
2014-03-18T08:27:46.250Z
2014-03-18T08:27:46.250Z
R B
<p>Following the idea of user <a href="https://cstheory.stackexchange.com/users/21001/r-b">R B</a> pointed out in the comment, I think the following example may have disproved the conjecture in the question.</p>

<p>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.</p>

<p><img src="https://i.sstatic.net/AjY92.png" alt="enter image description here"></p>

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

<p>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?</p>

CC BY-SA 3.0
2014-03-18T01:02:54.060Z
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.
JimN
CC BY-SA 3.0
2014-03-18T01:06:45.703Z
@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
CC BY-SA 3.0
2014-03-18T01:12:43.013Z
I don't think I changed your ratio, since your example of 32 vertices used 14 vertices in the transversal... no?
JimN
CC BY-SA 3.0
2014-03-18T01:17:14.673Z
@JimNastos No, 7/16=14/32. But your made it simpler.
Peng Zhang
CC BY-SA 3.0
2014-03-18T00:42:26.933Z
2014-03-18T00:42:26.933Z
2017-04-13T12:32:28.080Z
Peng Zhang
<p>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. </p>

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

<p>We consider gneral simple graphs here. However, any results of subclasses of simple graphs are welcome.</p>

<p><strong>Thoughts:</strong>
$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$.</p>

<p>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 <a href="https://cstheory.stackexchange.com/users/21001/r-b">R B</a> and <a href="https://cstheory.stackexchange.com/users/2414/jim-nastos">Jim Nastos</a>, we have an example on 16 vertices and whose minimal transverval has 7 vertices.</p>

<p><img src="https://i.sstatic.net/v9lti.png" alt="enter image description here"></p>

<p><strong>Introduction and why I am interested in $P_4$-transversal of graphs.</strong></p>

<p>Study of $P_4$-transversal is a part of study of $P_4$-structures of graphs, which plays an important role in the "<a href="http://en.wikipedia.org/wiki/Strong_perfect_graph_theorem" rel="nofollow noreferrer">Strong Perfect Graph Theorem</a>". $P_4$-transversal of perfect graphs and chordal graphs were studied in <a href="http://www.sciencedirect.com/science/article/pii/S0012365X99003003" rel="nofollow noreferrer">perfect graph</a> and <a href="http://www.sciencedirect.com/science/article/pii/S0012365X07008151" rel="nofollow noreferrer">chordal graph</a>.</p>

<p>$P_4$ is a path of 4 vertices. A $P4$-free graphs is called a <a href="http://en.wikipedia.org/wiki/Cograph" rel="nofollow noreferrer">cograph</a>, 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.  </p>

CC BY-SA 3.0
2014-03-18T00:02:21.350Z
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
CC BY-SA 3.0
2014-03-18T00:03:42.223Z
@RB Sorry for the misunderstanding. We consider induced P4. Therefore, there is no induced P4 in a complete graph.
Peng Zhang
CC BY-SA 3.0
2014-03-18T00:23:05.600Z
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
CC BY-SA 3.0
2014-03-18T00:44:25.460Z
@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
<graph-theory><graph-algorithms><co.combinatorics><cograph>
On the size of P4-transversals of graphs
Peng Zhang
# On the size of P4-transversals of graphs

(Asked by: username_0 on 2014-03-17)

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 [username_1](https://cstheory.stackexchange.com/users/21001/r-b) and [Jim Nastos](https://cstheory.stackexchange.com/users/2414/jim-nastos), we have an example on 16 vertices and whose minimal transverval has 7 vertices.

![enter image description here](https://i.sstatic.net/v9lti.png)

**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](http://en.wikipedia.org/wiki/Strong_perfect_graph_theorem)". $P\_4$-transversal of perfect graphs and chordal graphs were studied in [perfect graph](http://www.sciencedirect.com/science/article/pii/S0012365X99003003) and [chordal graph](http://www.sciencedirect.com/science/article/pii/S0012365X07008151).

$P\_4$ is a path of 4 vertices. A $P4$-free graphs is called a [cograph](http://en.wikipedia.org/wiki/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.

**Tags:** graph-theory, graph-algorithms, co.combinatorics, cograph

> **Comments:**
> **username_1**: 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.  
> **username_0**: @RB Sorry for the misunderstanding. We consider induced P4. Therefore, there is no induced P4 in a complete graph.  
> **username_1**: 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?  
> **username_0**: @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?  

---

## 3 answers

### Answer by username_2 on 2014-03-18. Score: 2 | Accepted answer

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 username_0'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...?

> **Comments:**
> **username_1**: the ratio is indeed 1, see my answer.  

---

### Answer by username_1 on 2014-03-18. Score: 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$.

> **Comments:**
> **username_2**: 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.)  
> **username_0**: @username_2astos 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.  
> **username_0**: 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.  
> **username_1**: @username_2astos, 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$.  
> **username_2**: @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.  
> **username_2**: @RB Oh, wait, I think if your norm was $|.|_1$, then we'd be talking about the standard graph cartesian product... but your interpretation of using $|.|_\infty$ is different and might coincide with the original construction... I'm not sure  
> **username_2**: @RB After sleeping on it, yes, your measure of using $|.|\infty$ is identical to the graph substitution construction. But I've never seen that referred to as a cartesian product on graphs.  

---

### Answer by username_0 on 2014-03-18. Score: 1

Following the idea of user [username_1](https://cstheory.stackexchange.com/users/21001/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](https://i.sstatic.net/AjY92.png)

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?

> **Comments:**
> **username_2**: 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.  
> **username_0**: @username_2astos Thanks a lot. So the ratio can be pushed up to 7/16. Maybe the upperbound of the ratio is 1/2?  
> **username_2**: I don't think I changed your ratio, since your example of 32 vertices used 14 vertices in the transversal... no?  
> **username_0**: @username_2astos No, 7/16=14/32. But your made it simpler.  

---

