On the feedback number of 3-uniform hypergraph
Zhuo Diao Zhongzheng Tang

my
mylabel

(my)


my


my2
mylabel2

(my2)
 

my2


my3
mylabel3

(my3)



my3






On the feedback number of 3-uniform hypergraph
    Zhuo Diao ^aCorresponding author. E-mail: diaozhuo@amss.ac.cn  Zhongzheng Tang ^b,c,d

    
 ^a School of Statistics and Mathematics, Central University of Finance and Economics
Beijing 100081, China

^b Academy of Mathematics and Systems Science, Chinese Academy of Sciences

 Beijing 100190, China

 ^c School of Mathematical Sciences, University of Chinese Academy of Sciences

 Beijing 10049, China

 ^d Department of Computer Science, City University of Hong Kong

 Hong Kong, China 

==================================================================================================================================================================================================================================================================================================================================================================================================================






Let H=(V,E) be a hypergraph with vertex set V and edge set E. S⊆ V is a feedback vertex set (FVS) of H if H∖ S has no cycle and τ_c(H) denote the minimum cardinality of a FVS of H. In this paper, we prove (i) if H is a linear 3-uniform hypergraph with m edges, then τ_c(H)≤ m/3. (ii) if H is a 3-uniform hypergraph with m edges, then τ_c(H)≤ m/2 and furthermore, the equality holds on if and only if every component of H is a 2-cycle.


Let H=(V,E) be a hypergraph with vertex set V and edge set E. A⊆ E is a feedback edge set (FES) of H if H∖ A has no cycle and τ_c'(H) denote the minimum cardinality of a FES of H. In this paper, we prove if H is a 3-uniform hypergraph with p components, then τ_c'(H)≤ 2m-n+p.




Keywords: Feedback vertex set (FVS); Feedback edge set (FES); 3-uniform hypergraph





§ HYPERGRAPHS


Let H=(V,E) be a hypergraph with vertex set V and edge set E. Hypergraph H is called linear if |e∩ f|≤1 for any distinct edges e,f∈ E, and 3-uniform if |e|=3 for each e∈ E. Let k≥ 2 be an integer. A cycle of length k is a sequence {v_1e_1v_2e_2...v_ke_kv_1} with: (1) {e_1, e_2,..., e_k} are distinct edges of H. (2) {v_1, v_2,..., v_k} are distinct vertices of H. (3) {v_i,v_i+1}⊆ e_i for each i∈ [k], here v_k+1=v_1. <cit.>


We say S⊆ V is a feedback vertex set (FVS) of H if H∖ S has no cycle and τ_c(H) denote the minimum cardinality of a FVS of H.

We say A⊆ E is a feedback edge set (FES) of H if H∖ A has no cycle and τ_c'(H) denote the minimum cardinality of a FES of H.

Obviously for any hypergraph H=(V,E), we have τ_c(H)≤τ_c'(H).

There are many literatures about the feedback vertex/edge number in hypergraph theory. <cit.><cit.><cit.><cit.><cit.><cit.><cit.>








§ THE FEEDBACK VERTEX NUMBER




 §.§ The bound for linear hypergraph


In this subsection, for linear 3-uniform hypergraph, we give the bound of the feedback vertex number.


Let H be a linear 3-uniform hypergraph with m edges. Then τ_c(H)≤ m/3.


Suppose the theorem fails. Let us take out the counterexample H=(V,E) with minimum number of edges, thus τ_c(H)> m/3.
Obviously m≥ 3 and without loss of generality, we can assume H has no isolated vertex. We will break the proof into a series of claims.


  Every edge in E is contained in some cycle in H.


If there exists e∈ E which doesn't belong to any cycle of H. Then τ_c(H)= τ_c(H∖ e). Because H=(V,E) is the counterexample with minimum number of edges, we have τ_c(H∖ e)≤ (m-1)/3. Thus τ_c(H)≤ m/3, this is a contradiction with τ_c(H)> m/3.


 ∀ v∈ H, d(v)≤ 2.


If there exists v∈ V with d(v)≥3 in H, then τ_c(H∖ v)≤ (m-d(v))/3≤ (m-3)/3 because H=(V,E) is the counterexample with minimum number of edges. Considering a minimum FVS S of H'=H∖ v, we have S⊆ V∖ v and |S|≤ (m-3)/3. Thus S∪ v is a FVS for H and |S∪ v|= |S|+1≤ m/3, this is a contradiction with τ_c(H)> m/3.


 H is triangle free.


If there exists C=v_1e_1v_2e_2v_3e_3v_1 in H, then τ_c(H∖{e_1,e_2,e_3})≤ (m-3)/3 because H=(V,E) is the counterexample with minimum number of edges. Considering a minimum FVS S of H'=H∖{e_1,e_2,e_3},  we have S⊆ V and |S|≤ (m-3)/3. Due to claim <ref>, we have S∪ v_1 is a FVS for H and |S∪ v_1|≤ |S|+1≤ m/3, this is a contradiction with τ_c(H)> m/3.


 H is 2-regular.


Due to claim <ref>, we just need to prove there is no vertex with degree 1. If there exists v∈ V with d(v)= 1 in H, we could assume v∈ e_1. Due to claim <ref> and <ref>, we can assume there exists C=v_1e_1v_2e_2v_3e_3v_4...e_kv_1 with k≥ 4 in H and e_1= {v_1,v,v_2}. Then τ_c(H∖{e_1,e_2,e_3})≤ (m-3)/3 because H=(V,E) is the counterexample with minimum number of edges. Considering a minimum FVS S of H'=H∖{e_1,e_2,e_3},  we have S⊆ V and |S|≤ (m-3)/3.  Due to claim <ref> and d(v)=1, we have S∪ v_3 is a FVS for H and |S∪ v_3|≤ |S|+1≤ m/3, this is a contradiction with τ_c(H)> m/3.


 There is no cycle with length 4 in H.


Suppose on the contrary, there exists C=v_1e_1v_2e_2v_3e_3v_4e_4v_1 in H, we have e_1∩ e_3= e_2∩ e_4=∅ due to claim <ref>. We can assume e_1={v_1,u_1,v_2}, e_2={v_2,u_2,v_3}, e_3={v_3,u_3,v_4}, e_4={v_4,u_4,v_1} and these vertices are distinct. Due to claim <ref>, we can assume u_1∈ e_5≠ e_1, u_2∈ e_6≠ e_2 and u_3∈ e_7≠ e_3. Due to claim <ref>,we have e_5≠ e_6, e_6≠ e_7. 

If e_5= e_7, we have τ_c(H∖{e_1,e_2,e_3,e_4,e_5,e_6})≤ (m-6)/3 because H=(V,E) is the counterexample with minimum number of edges. Considering a minimum FVS S of H'=H∖{e_1,e_2,e_3,e_4,e_5,e_6},  we have S⊆ V and |S|≤ (m-6)/3. Due to claim <ref>, we have S∪ u_2∪ u_4 is a FVS for H and |S∪ u_2∪ u_4|≤ |S|+2≤ m/3, this is a contradiction with τ_c(H)> m/3. See Figure <ref> for an illustration.

If e_5≠ e_7, we have τ_c(H∖{e_1,e_2,e_3,e_4,e_5,e_7})≤ (m-6)/3 because H=(V,E) is the counterexample with minimum number of edges. Considering a minimum FVS S of H'=H∖{e_1,e_2,e_3,e_4,e_5,e_7},  we have S⊆ V and |S|≤ (m-6)/3. Due to claim <ref>, we have S∪ u_1∪ u_3 is a FVS for H and |S∪ u_1∪ u_3|≤ |S|+2≤ m/3, this is a contradiction with τ_c(H)> m/3. See Figure <ref> for an illustration.




Let C=(V',E')=v_1e_1v_2e_2… v_ke_kv_1 be a shortest cycle in H. For each i∈[k], suppose that e_i={v_i,u_i,v_i+1}, where v_k+1=v_1. Due to claim <ref> and <ref>, we have k≥ 5. Because C is the shortest cycle, for each index pair {i≠ j}⊆ [k], if e_i and e_j are not adjacent in C, we have e_i∩ e_j=∅. 


 k≢03


If k≡03, we can assume k=3t with t≥ 2. Then τ_c(H∖ E')≤ (m-3t)/3 because H=(V,E) is the counterexample with minimum number of edges. Considering a minimum FVS S of H'=H∖ E',  we have S⊆ V and |S|≤ (m-3t)/3. Due to claim <ref>, we have S∪v_3,v_6,…,v_3i,…,v_3t is a FVS for H and |S∪v_3,v_6,…,v_3i,…,v_3t|≤ |S|+t≤ m/3, this is a contradiction with τ_c(H)> m/3. See Figure <ref> for an illustration.


 k≢13


If k≡13, we can assume k=3t+1 with t≥ 2. Due to claim <ref>, <ref> and <ref>, we have u_1∈ e_3t+2≠ e_1,u_3∈ e_3t+3≠ e_3 and e_1,e_2,e_3...e_3t+1,e_3t+2,e_3t+3 are distinct. Then τ_c(H∖{E',e_3t+2,e_3t+3}≤ (m-3t-3)/3 because H=(V,E) is the counterexample with minimum number of edges. Considering a minimum FVS S of H'=H∖{E',e_3t+2,e_3t+3},  we have S⊆ V and |S|≤ (m-3t-3)/3. Due to claim <ref>, we have S∪u_1,u_3,v_6,…,v_3i,…,v_3t is a FVS for H and |S∪u_1,u_3,v_6,…,v_3i,…,v_3t|≤ |S|+t+1≤ m/3, this is a contradiction with τ_c(H)> m/3. See Figure <ref> for an illustration.


 k≢23


If k≡23, we can assume k=3t+2 with t≥ 1. Due to claim <ref> and the shortest cycle of C , we have u_1∈ e_3t+3≠ e_1 and e_1,e_2,e_3...e_3t+1,e_3t+2,e_3t+3 are distinct. Then τ_c(H∖{E',e_3t+3}≤ (m-3t-3)/3 because H=(V,E) is the counterexample with minimum number of edges. Considering a minimum FVS S of H'=H∖{E',e_3t+3},  we have S⊆ V and |S|≤ (m-3t-3)/3. Due to claim <ref>, we have S∪u_1,v_4,…,v_3i+1,…,v_3t+1 is a FVS for H and |S∪u_1,v_4,…,v_3i+1,…,v_3t+1|≤ |S|+t+1≤ m/3, this is a contradiction with τ_c(H)> m/3. See Figure <ref> for an illustration.




Above all, we have claim <ref>,<ref> and <ref>, this is impossible. Thus our assumption doesn't hold on. We finish our proof.



















  


See Figure <ref> for illustrations of five linear 3-uniform  hypergraphs attaining the upper bound.  It is easy to prove that the maximum degree of every extremal hypergraph (those H with τ_c(H)= m/3) is at most three. It would be interesting to characterize all extremal hypergraphs for Theorem <ref>.









 §.§ The bounds for general hypergraph


In this subsection, for general 3-uniform hypergraph, we give the bound of the feedback vertex number.


Let H be a 3-uniform hypergraph with m edges. Then τ_c(H)≤ m/2.
Furthermore, the equality holds on if and only if every component of H is a 2-cycle.



First, we will prove τ_c(H)≤ m/2. Suppose the theorem fails. Let us take out the counterexample H=(V,E) with minimum number of edges, thus τ_c(H)> m/2. Without loss of generality, we can assume H has no isolated vertex. We will get a contradiction through two claims.


  Every edge in E is contained in some cycle in H.


If there exists e∈ E which doesn't belong to any cycle of H. Then τ_c(H)= τ_c(H∖ e). Because H=(V,E) is the counterexample with minimum number of edges, we have τ_c(H∖ e)≤ (m-1)/2. Thus τ_c(H)< m/2, this is a contradiction with τ_c(H)> m/2.


 ∀ v∈ H, d(v)≤ 1.


If there exists v∈ V with d(v)≥ 3 in H, then τ_c(H∖ v)≤ (m-d(v))/2≤ (m-2)/2 because H=(V,E) is the counterexample with minimum number of edges. Considering a minimum FVS S of H'=H∖ v, we have S⊆ V∖ v and |S|≤ (m-2)/2. Thus S∪ v is a FVS for H and |S∪ v|= |S|+1≤ m/2, this is a contradiction with τ_c(H)> m/2.

The above two claims lead to a contradiction immediately. 


Second, we will prove the equality holds on if and only if every component of H is a 2-cycle. 

Sufficiency: This is obvious.

Necessity: Let H=(V,E) be a 3-uniform hypergraph with τ_c(H)= m/2. Without loss of generality, we can assume H is connected and we just need to prove H is a 2-cycle. We will finish the proof through a series of claims.


  Every edge in E is contained in some cycle in H.


If there exists e∈ E which doesn't belong to any cycle of H. Then τ_c(H)= τ_c(H∖ e). Because H=(V,E) is the counterexample with minimum number of edges, we have τ_c(H∖ e)≤ (m-1)/2. Thus τ_c(H)< m/2, this is a contradiction with τ_c(H)= m/2.


 ∀ v∈ H, d(v)≤ 2.


If there exists v∈ V with d(v)≥ 3 in H, then τ_c(H∖ v)≤ (m-d(v))/2≤ (m-3)/2 because H=(V,E) is the counterexample with minimum number of edges. Considering a minimum FVS S of H'=H∖ v, we have S⊆ V∖ v and |S|≤ (m-3)/2. Thus S∪ v is a FVS for H and |S∪ v|= |S|+1≤ (m-1)/2< m/2, this is a contradiction with τ_c(H)= m/2.


 ∀ v∈ H, if d(v)= 2, then τ_c(H∖ v)= (m-2)/2.


Combining the next inequality and τ_c(H)= m/2, this claim is obvious.


    τ_c(H)≤τ_c(H∖ v)+1≤ (m-2)/2+1= m/2


Now τ_c(H)= m/2, according to Theorem <ref>, H is not linear, thus H contains a 2-cycle: v_1e_1v_2e_2v_1. If H is not a 2-cycle, by claim <ref>, we can assume e_1={v_1,u,v_2},u∈ e, {e,e_1,e_2} are three distinct edges. By claim <ref>, d(u)= 2, τ_c(H∖ u)= (m-2)/2. Notice that in H∖ u, e_2 contains two 1- degree vertices, thus e_2 can not be contained in any cycle. Thus, we have the next inequality, which is a contradiction with τ_c(H∖ u)= (m-2)/2.


    τ_c(H∖ u)=τ_c(H∖ u∖ e_2)≤ (m-3)/2< (m-2)/2


Above all, we finish the theorem's proof.






§ THE FEEDBACK EDGE NUMBER


In this section, for general 3-uniform hypergraph, we give the bound of the feedback edge number.


Let H=(V,E) be a  3-uniform hypergraph with p components, then τ_c'(H)≤ 2m-n+p.










Before proving the theorem above, we will prove a series of lemmas which are very useful.


For every 3-uniform connected hypergraph H(V,E), n≤ 2m+1 holds on.



We prove this lemma by induction on m. When m=0, H(V,E) is an isolate vertex, n≤ 2m+1 holds on.
Assume this lemma holds on for m≤ k. When m=k+1, take arbitrarily one edge e and consider the subgraph H∖ e.
obviously, H∖ e has at most three components. Assume H∖ e has p components H_i(V_i,E_i) and n_i=|V_i|, m_i=|E_i| for each i∈{1,...,p}. Then by our induction, n_i≤ 2m_i+1 holds on. So we have


    n=n_1+...n_p≤ 2m_1+...2m_p+p=2(m-1)+p=2m+p-2≤ 2m+1


By induction, we finish our proof.



For every 3-uniform connected hypergraph H(V,E), n=2m+1 if and only if H is a hypertree.



sufficiency: if H is a hypertree, we prove n=2m+1 by induction on m. When m=0, H(V,E) is an isolate vertex, n=2m+1 holds on.
Assume this lemma holds on for m≤ k. When m=k+1, take arbitrarily one edge e and consider the subgraph H∖ e.
Because H is a hypertree, H∖ e has exactly three components, denoted by H_i(V_i,E_i) and n_i=|V_i|, m_i=|E_i| for each i∈{1,2,3}. Because every component is a hypertree, thus by our induction, n_i= 2m_i+1 holds on. So we have


    n=n_1+n_2+n_3=2m_1+2m_2+2m_3+3=2(m-1)+3=2m+1


By induction, we finish the sufficiency proof.


necessity: We prove by contradiction. If H is not a hypertree, H contain a cycle C. Take arbitrarily one edge e in C and consider the subgraph H∖ e. obviously, H∖ e has at most two components. Assume H∖ e has p components H_i(V_i,E_i) and n_i=|V_i|, m_i=|E_i| for each i∈{1,...,p}. Then by lemma <ref>, n_i≤ 2m_i+1 holds on. So we have


    n=n_1+...n_p≤ 2m_1+...2m_p+p=2(m-1)+p=2m+p-2≤ 2m< 2m+1


which is a contradiction with n=2m+1. Thus H is a hypertree and we finish our necessity proof.





















Next we will prove the main theorem:


Let H=(V,E) be a 3-uniform hypergraph with p components, then τ_c'(H)≤ 2m-n+p.


  Pick arbitrarily a minimum FES A⊆ E, then τ_c'(H)=|A|. Suppose that H∖ A contains exactly k components H_i=(V_i,E_i), i=1,…,k. It follows from Lemma <ref> that n_i=2m_i+1 for each i∈ [k]. Thus n=∑_i∈ [k]n_i= 2∑_i∈ [k]m_i+k= 2(m-τ_c'(H))+k, which means 2τ_c'(H)= 2m-n+k. To establish the lemma, it suffices to prove  k≤τ_c'(H)+ p.

 In case of  τ_c'(H)=0, we have A=∅ and k=p=τ_c'(H)+p.  In case of  τ_c'(H)≥ 1, suppose that A={e_1,...,e_|A|}. Because A is a minimum FES of H,  for each i∈ [|A|], there is a cycle C_i in H∖ (A∖{e_i}) such that e_i∈ C_i. Considering H∖ A being obtained from H be removing e_1,e_2,…,e_|A| sequentially, for i=1,…,|A|, since |e_i|=3, the presence of C_i implies that the removal of e_i can create at most one more component. Therefore we have  k≤ p+|A| as desired.





§ CONCLUSION AND FUTURE WORK


Conclusion: (i) if H is a linear 3-uniform hypergraph with m edges, then τ_c(H)≤ m/3. (ii) if H is a 3-uniform hypergraph with m edges, then τ_c(H)≤ m/2 and furthermore, the equality holds on if and only if every component of H is a 2-cycle. (iii) if H is a 3-uniform hypergraph with p components, then τ_c'(H)≤ 2m-n+p.


Future work: for linear 3-uniform hypergraph, it would be interesting to characterize all extremal hypergraphs (those H with τ_c(H)= m/3).




