Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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|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 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 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 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 at 0:44
add comment

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

Thoughts...?

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

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|improve this answer
1  
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 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 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 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 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 at 8:51
show 2 more comments

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|improve this answer
1  
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 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 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 at 1:12
    
@JimNastos No, 7/16=14/32. But your made it simpler. –  Peng Zhang Mar 18 at 1:17
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.