# 圖的三角形覆蓋與裝填

Student thesis: Doctoral Thesis

## Detail(s)

Awarding Institution City University of Hong Kong Xiaohua JIA (Supervisor) 24 Jun 2020

## 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 3-vertex 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 edge-disjoint triangles in G, respectively. Tuza conjectured that τt(G)/νt(G) ≤ 2 holds for every simple graph G. Edge-weighted graph (G, w) is a generalization of simple graph G, where w ∈ ZE 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 edge-weighted graph. We ﬁrstly prove the theoretical results on hypergraphs. Then, using these results, we design polynomial-time 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 edge-weighted 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 triangle-edge 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 = Ω(n2), 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.

## Research areas

• Tuza’s Conjecture, Hypergraph, Total Dual Integrality, Random Graphs