Covering and Packing Triangles in Graphs
圖的三角形覆蓋與裝填
Student thesis: Doctoral Thesis
Author(s)
Related Research Unit(s)
Detail(s)
Awarding Institution  

Supervisors/Advisors 

Award date  24 Jun 2020 
Link(s)
Permanent Link  https://scholars.cityu.edu.hk/en/theses/theses(b53645c07b6141b8a73607a5f801b02e).html 

Other link(s)  Links 
Abstract
This thesis is motivated by an unsolved conjecture in graph theory which was proposed by Hungarian mathematician Zsolt Tuza in 1981. Given a simple graph G = (V, E) where V is the vertex set and E is the edge set, a triangle in G is a 3vertex complete subgraph. A subset of E is called a triangle cover if it intersects each triangle of G. Let τ_{t}(G) and ν_{t}(G) denote the minimum cardinality of a triangle cover of G and the maximum number of pairwise edgedisjoint triangles in G, respectively. Tuza conjectured that τ_{t}(G)/ν_{t}(G) ≤ 2 holds for every simple graph G. Edgeweighted graph (G, w) is a generalization of simple graph G, where w ∈ Z^{E} is an edge weight function. Let τ_{t}(G, w) and ν_{t}(G, w) be the minimum weight of triangle cover and the maximum cardinality of triangle packing of (G, w), respectively. Chapuy et al. conjectured that τ_{t}(G, w)/ν_{t}(G, w) ≤ 2 holds for every simple graph G and edge weight w.
The goal of this thesis is to partially answer the following questions which are highly related to the above Tuza's conjecture: What are the graph topologies which ensure the inequality τ_{t}(G, w)/ν_{t}(G, w) ≤ 2? What are the graph topologies which ensure the equality τ_{t}(G, w)= ν_{t}(G, w)? How good can the upper bound of τ_{t}(G)/ν_{t}(G) be on random graph models G(n, p) and G(n, m)?
In Chapter 1, we brieﬂy introduce the background of Tuza's conjecture and survey related work in various aspects.
In Chapter 2, we consider the weighted generalization of Tuza's conjecture on edgeweighted graph. We ﬁrstly prove the theoretical results on hypergraphs. Then, using these results, we design polynomialtime combinatorial algorithms for ﬁnding triangle covers with small weights. These algorithms imply new sufﬁcient conditions for the weighted version of Tuza's conjecture on covering and packing triangles.
In Chapter 3, we focus on weighted triangle covering in edgeweighted graphs. The characteristic vector x of each triangle cover in G is an integral solution of the polyhedron π = {x : Ax ≥ 1, x ≥ 0}, where A is the triangleedge incidence matrix of G. We obtain graph properties that are necessary for the total dual integrality of system Ax ≥ 1, x ≥ 0, as well as those for the total unimodularity of matrix A and the integrality of polyhedron π. These necessary conditions are shown to be sufﬁcient and the three notions of integrality coincide when restricted to planar graphs.
In Chapter 4, we consider Tuza's conjecture on dense random graphs. We prove that under G(n, p) model with p = Ω(1), for any 0 < ε < 1, τ_{t}(G) ≤ 1.5(1 + ε)ν_{t}(G) holds with high probability, and under G(n, m) model with m = Ω(n^{2}), for any 0 < ε < 1, τ_{t}(G) ≤ 1.5(1 + ε)ν_{t}(G) holds with high probability. In some sense, the derived results provide conclusions that are stronger than Tuza's conjecture.
In Chapter 5, we summarize the main results obtained in the thesis and discuss some possible research directions for future work.
The goal of this thesis is to partially answer the following questions which are highly related to the above Tuza's conjecture: What are the graph topologies which ensure the inequality τ_{t}(G, w)/ν_{t}(G, w) ≤ 2? What are the graph topologies which ensure the equality τ_{t}(G, w)= ν_{t}(G, w)? How good can the upper bound of τ_{t}(G)/ν_{t}(G) be on random graph models G(n, p) and G(n, m)?
In Chapter 1, we brieﬂy introduce the background of Tuza's conjecture and survey related work in various aspects.
In Chapter 2, we consider the weighted generalization of Tuza's conjecture on edgeweighted graph. We ﬁrstly prove the theoretical results on hypergraphs. Then, using these results, we design polynomialtime combinatorial algorithms for ﬁnding triangle covers with small weights. These algorithms imply new sufﬁcient conditions for the weighted version of Tuza's conjecture on covering and packing triangles.
In Chapter 3, we focus on weighted triangle covering in edgeweighted graphs. The characteristic vector x of each triangle cover in G is an integral solution of the polyhedron π = {x : Ax ≥ 1, x ≥ 0}, where A is the triangleedge incidence matrix of G. We obtain graph properties that are necessary for the total dual integrality of system Ax ≥ 1, x ≥ 0, as well as those for the total unimodularity of matrix A and the integrality of polyhedron π. These necessary conditions are shown to be sufﬁcient and the three notions of integrality coincide when restricted to planar graphs.
In Chapter 4, we consider Tuza's conjecture on dense random graphs. We prove that under G(n, p) model with p = Ω(1), for any 0 < ε < 1, τ_{t}(G) ≤ 1.5(1 + ε)ν_{t}(G) holds with high probability, and under G(n, m) model with m = Ω(n^{2}), for any 0 < ε < 1, τ_{t}(G) ≤ 1.5(1 + ε)ν_{t}(G) holds with high probability. In some sense, the derived results provide conclusions that are stronger than Tuza's conjecture.
In Chapter 5, we summarize the main results obtained in the thesis and discuss some possible research directions for future work.
 Tuza’s Conjecture, Hypergraph, Total Dual Integrality, Random Graphs