Sparse cuts, matching-cuts and leafy trees in graphs

P.S. Bonsma

Research output: ThesisPhD Thesis - Research UT, graduation UT

187 Downloads (Pure)


In this thesis, three different graph concepts are studied. A graph $(V,E)$ consists of a set of vertices $V$ and a set of edges $E$. Graphs are often used as a model for telecommunication networks, where the nodes of the network are represented by the vertices, and an edge is present between two vertices if the corresponding nodes are joined by a direct connection in the network. The two vertices joined by an edge are called its end vertices, and these two vertices are neighbors of each other. The degree of a vertex is its number of neighbors. The problems in this thesis can be explained and motivated using applications in the area of network design and analysis, which is done in Chapter 1. This chapter also contains the basic definitions that will be used. The first problem we study is the problem of finding sparsest cuts of a graph. For a non-empty proper subset of the vertices $S \subset V$ ,$[S,\overline{S}]$ denotes the set of edges with one end vertex in $S$, which is an \emph{edge cut}. An edge cut $[S \overline{S}]$ is a sparsest cut if its density ${|[S,\overline{S}]| \over |S||\overline{S}|}$ is minimum, over all edge cuts of the graph. Sparsest cuts are closely related to all-to-all flows in networks, and we also discuss an application related to network reliability. In general, the problem of finding sparsest cuts or calculating their density is ${\cal NP}$-hard. However, for three classes of well-structured graphs we characterize the sparsest cuts in Chapter 2. These classes are Cartesian product graphs, unit interval graphs and complete bipartite graphs. Secondly, matching-cuts are studied. A matching is a set of edges that pairwise have no end vertices in common, and a matching-cut is an edge cut that is also a matching. The problem of deciding whether a graph admits a matching-cut is ${\cal NP}$-complete. In Chapter 3 we show that the problem remains ${\cal NP}$-complete when restricted to planar graphs with maximum degree four. We show that the problem can be decided in polynomial time for a number of graph classes such as claw-free graphs, co-graphs, outerplanar graphs, and graph classes with bounded treewidth in general. In Chapter 4, graphs without a matching-cut are studied, which are called (matching) immune. Farley and Proskurowski proved that for all immune graphs on $n$ vertices with $m$ edges, $m \ge \lceil 3(n-1)/2\rceil$, and constructed a large class of immune graphs attaining this lower bound for every value of $n$, called $ABC$ graphs. In Chapter 4, we prove their conjecture that all matching immune graphs with $m = \lceil 3(n-1)/2\rceil$ are $ABC$ graphs. The third topic of this thesis is spanning trees with many leaves. A spanning tree of a graph is a connected subgraph that contains all vertices, with a minimum number of edges. A leaf of a spanning tree is a vertex with degree one. Finding spanning trees with many leaves is another problem that often occurs in network design. In Chapter 5 we show that connected graphs on $n$ vertices, without triangles, with minimum degree at least three, have a spanning tree with at least $(n+4)/3$ leaves. In addition we present a more general but weaker result; we show that connected graphs on $n$ vertices, with minimum degree at least three, have a spanning tree with at least $(2n-D+12)/7$ leaves, where $D$ is the number of diamonds in the graph induced by degree three vertices (a diamond is a $K_4$ minus an edge). Both results are best possible and constructive. In Chapter 6 we give an algorithm for deciding whether a graph on $n$ vertices has a spanning tree with at least $k$ leaves, using the second result from Chapter 5. This problem is ${\cal NP}$-complete. The complexity of the algorithm is $g(n)+ f(k)$, where $g(n)$ is a polynomial and $f(k) \in O(8.12^k)$. It follows that this is a Fixed Parameter Tractable (FPT) algorithm, when $k$ is viewed as the parameter of the problem. This is the current fastest FPT algorithm for this problem.
Original languageUndefined
Awarding Institution
  • University of Twente
  • Broersma, Hajo, Supervisor
  • Woeginger, Gerhard, Supervisor
Award date28 Jun 2006
Place of PublicationEnschede
Print ISBNs90-365-2370-2
Publication statusPublished - 28 Jun 2006


  • EWI-8134
  • METIS-237604
  • IR-57117

Cite this