Some results about minimum cuts, treewidth and hamiltonian circuits

Abstract

In this thesis, we study various graph theoretic structures. One of the topics we study is the minimum cuts in a graph. We relate the number of minimum cuts in a weighted undirected graph with various structural parameters of the graph. In particular, we upper-bound the number of minimum cuts in terms of the radius, diameter, minimum degree, maximum degree, chordality, girth, etc., of the graph. We also study the relation between the size of the minimum cuts and the minimum separators in a special class of graphs called the chordal graphs. Another graph parameter we study is the treewidth of a graph. Treewidth can be seen as the optimum value of various max-min problems. For example, it is the minimum of the maximum clique sizes over all chordal graphs which are supergraphs of the given graph. We define a certain generalized expansion property of a graph and provide a lower bound for the treewidth in terms of this expansion property. Based on this lower bound, we derive several consequences, ranging from a lower bound for the treewidth in terms of the girth and average degree to certain structural properties of graphs. Finally, we consider a parameterized variation of the famous asymmetric traveling salesman problem, which is to find the minimum cost Hamiltonian tour in a complete weighted directed graph. We give a constant-factor approximation algorithm for the asymmetric traveling salesman problem in graphs with costs on the edges satisfying ?-parameterized triangle inequality (?-asymmetric graphs) for ? ? (1, ?). (The graph is said to satisfy ?-parameterized triangle inequality iff c(u, v) ? ?(c(u, w) + c(w, v)) ? u, v, w ? V.) We also explore the structure of ?-asymmetric graphs. In particular, we study the ?-ratio of edge costs in a ?-asymmetric graph. It may be noted that ? is interesting since it is an upper bound for the ratio of the cost of an arbitrary Hamiltonian circuit to the cost of an optimum Hamiltonian circuit.