Study of some graph theoretic problems via vertex orderings

Abstract

Graph traversal algorithms like breadth-first search and depth-first search typically produce an ordering of the vertices of the input graph. Properties of these vertex orderings often provide new insights about the structure of the graphs under consideration. The existence of vertex orderings that satisfy some special properties characterizes some well-known graph classes like chordal graphs, comparability graphs and cocomparability graphs. Moreover, the availability of such a characterization for a class of graphs often helps us obtain efficient recognition algorithms for the class and also efficient algorithms for a multitude of optimization problems on graphs belonging to the class. As a contribution to this line of research, we show how the vertex ordering approach is useful in the study of some structural and algorithmic questions about graphs and digraphs. Threshold graphs are a class of graphs that have many equivalent definitions and have appli- cations in integer programming and set packing problems. A graph is said to have a threshold cover of size k if its edges can be covered using k threshold graphs. Let th(G) denote the least integer k such that G has a threshold cover of size k. In 1977, Chvátal and Hammer observed that th(G) ≥ χ(G∗), where G∗ is a suitably constructed auxiliary graph. They also asked the question of whether there is any graph G such that th(G) > χ(G∗). Cozzens and Leibowitz showed that for every k ≥ 4, there exists a graph G such that χ(G∗) = k but th(G) > k. Later, Raschle and Simon settled this question for the case k = 2, by proving that for any graph G such that χ(G∗) = 2, we have th(G) = χ(G∗). In the first part of this thesis, we show how the lexicographic method of Hell and Huang can be used to obtain a completely new and, we believe, simpler proof for this result. For the case when G is a split graph, our method yields a proof that is much shorter than the ones known in the literature. The problem of computing a minimum cardinality dominating set or absorbing set or kernel (an independent and absorbing set of a digraph), and the problems of computing a maximum cardinality independent set or kernel are all known to be NP-hard for general digraphs. In the second part of the thesis, we explore the algorithmic complexity of these problems in the well known class of interval digraphs. A digraph G is an interval digraph if a pair of intervals (Su, Tu) can be assigned to each vertex u of G such that (u, v) ∈ E(G) if and only if Su ∩ Tv 6 = ∅. Many different subclasses of interval digraphs have been defined and studied in the literature by restricting the kinds of pairs of intervals that can be assigned to the vertices. We observe that several of these classes, like interval catch digraphs, interval nest digraphs, adjusted interval v digraphs and chronological interval digraphs, are subclasses of the more general class of reflexive interval digraphs – which arise when we require that the two intervals assigned to a vertex have to intersect. Here we identify the class of reflexive interval digraphs as an important class of digraphs. We show that while the problems mentioned above are NP-complete, and even hard to approximate, on interval digraphs (even on some very restricted subclasses of interval digraphs called point-point digraphs, where the two intervals assigned to each vertex are required to be degenerate), they are all efficiently solvable, in most of the cases linear-time solvable, in the class of reflexive interval digraphs. We also provide a vertex ordering characterization for the class of reflexive interval digraphs and two structural characterizations for the class of point- point digraphs. The results we obtain improve and generalize several existing algorithms and structural results for subclasses of reflexive interval digraphs. Along the way, we also obtain some new results for undirected graphs as well. A vertex in a directed graph is said to have a large second neighborhood if it has at least as many second out-neighbors as out-neighbors. The Second Neighborhood Conjecture, first stated by Seymour, asserts that there is a vertex having a large second neighborhood in every oriented graph (a directed graph without loops or digons). In the third part of the thesis, we extend some results on this conjecture. It is straightforward to see that the conjecture is true for any oriented graph whose underlying undirected graph is bipartite. We extend this by showing that the conjecture holds for oriented graphs whose vertex set can be partitioned into an independent set and a 2-degenerate graph. Fisher proved the conjecture for tournaments and later Havet and Thomassé provided a different proof for the same using median orders of tournaments. Havet and Thomassé in fact showed the stronger statement that if a tournament contains no sink, then it contains at least two vertices with large second neighborhoods. Using their techniques, Fidler and Yuster showed that the conjecture remains true for tournaments from which either a matching or a star has been removed. Using the same tool of median orders, we extend this result to show that the conjecture holds even for tournaments from which both a matching and a star have been removed. This implies that a tournament from which a matching has been removed contains either a sink or two vertices with large second neighborhoods.