Covering and Packing Triangles in Graphs

圖的三角形覆蓋與裝填

Student thesis: Doctoral Thesis

View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Awarding Institution
Supervisors/Advisors
Award date24 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 briefly 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 firstly prove the theoretical results on hypergraphs. Then, using these results, we design polynomial-time combinatorial algorithms for finding triangle covers with small weights. These algorithms imply new sufficient 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 sufficient 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