Abstract
Original language  Undefined 

Awarding Institution 

Supervisors/Advisors 

Award date  28 Jun 2006 
Place of Publication  Enschede 
Publisher  
Print ISBNs  9036523702 
Publication status  Published  28 Jun 2006 
Keywords
 EWI8134
 METIS237604
 IR57117
Cite this
}
Sparse cuts, matchingcuts and leafy trees in graphs. / Bonsma, P.S.
Enschede : Ipskamp Printing, 2006. 175 p.Research output: Thesis › PhD Thesis  Research UT, graduation UT › Academic
TY  THES
T1  Sparse cuts, matchingcuts and leafy trees in graphs
AU  Bonsma, P.S.
PY  2006/6/28
Y1  2006/6/28
N2  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 nonempty 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 alltoall 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 wellstructured graphs we characterize the sparsest cuts in Chapter 2. These classes are Cartesian product graphs, unit interval graphs and complete bipartite graphs. Secondly, matchingcuts are studied. A matching is a set of edges that pairwise have no end vertices in common, and a matchingcut is an edge cut that is also a matching. The problem of deciding whether a graph admits a matchingcut 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 clawfree graphs, cographs, outerplanar graphs, and graph classes with bounded treewidth in general. In Chapter 4, graphs without a matchingcut 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(n1)/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(n1)/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 $(2nD+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.
AB  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 nonempty 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 alltoall 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 wellstructured graphs we characterize the sparsest cuts in Chapter 2. These classes are Cartesian product graphs, unit interval graphs and complete bipartite graphs. Secondly, matchingcuts are studied. A matching is a set of edges that pairwise have no end vertices in common, and a matchingcut is an edge cut that is also a matching. The problem of deciding whether a graph admits a matchingcut 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 clawfree graphs, cographs, outerplanar graphs, and graph classes with bounded treewidth in general. In Chapter 4, graphs without a matchingcut 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(n1)/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(n1)/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 $(2nD+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.
KW  EWI8134
KW  METIS237604
KW  IR57117
M3  PhD Thesis  Research UT, graduation UT
SN  9036523702
PB  Ipskamp Printing
CY  Enschede
ER 