On the Structure of Contractible Vertex Pairs in Chordal Graphs
An edge/non-edge in a k-connected graph is contractible if its contraction does not result in a graph of lower connectivity. We focus our study on contractible edges and non-edges in chordal graphs. Firstly, we characterize contractible edges in chordal graphs using properties of tree decompositions with respect to minimal vertex separators. Secondly, we show that in every chordal graph each non-edge is contractible. We also characterize non-edges whose contraction leaves a k-connected chordal graph. © 2009 Elsevier B.V. All rights reserved.
On the structure of contractible edges in k-connected partial k-trees
Contraction of an edge e merges its end points into a new single vertex, and each neighbor of one of the end points of e is a neighbor of the new vertex. An edge in a k-connected graph is contractible if its contraction does not result in a graph with lesser connectivity; otherwise the edge is called non-contractible. In this paper, we present results on the structure of contractible edges in k-trees and k-connected partial k-trees. Firstly, we show that an edge e in a k-tree is contractible if and only if e belongs to exactly one (k + 1) clique. We use this characterization to show that the graph formed by contractible edges is a 2-connected graph. We also show that there are at least {pipe}V(G){pipe} + k - 2 contractible edges in a k-tree. Secondly, we show that if an edge e in a partial k-tree is contractible then e is contractible in any k-tree which contains the partial k-tree as an edge subgraph. We also construct a class of contraction critical 2k-connected partial 2k-trees. © 2009 Springer.
A unified framework for bi(tri)connectivity and chordal augmentation
For a connected non-complete graph, a vertex separator is a subset of vertices whose deletion increases the number of connected components and the vertex connectivity of the graph refers to the size of a minimum vertex separator. A graph with the vertex connectivity k is said to be k-vertex connected. Given a k-vertex connected graph G, vertex connectivity augmentation determines a smallest set of edges whose augmentation to G makes it (k + 1)-vertex connected. In this paper, we report our study on connectivity augmentation in 1-connected graphs, 2-connected graphs, and k-connected chordal graphs. We first represent the graph under consideration using a "tree-like" graph. This tree is unique and explicitly captures the connectivity information of the graph. Using this tree, our proposed data structure maintains the set of equivalence classes based on an equivalence relation on the set of leaves of the tree. This partition determines a set of edges to be augmented to increase the connectivity of the graph by one. Based on our data structure, we present a new combinatorial analysis and an elegant proof of correctness of our linear-time algorithm for an optimum connectivity augmentation. The novelty is in the data structure which is a unified framework for all three augmentations. As far as the run-time analysis is concerned, given the associated tree, our approach yields an augmentation set in linear time. © 2013 World Scientific Publishing Company.
A novel data structure for biconnectivity, triconnectivity, and κ-tree augmentation
For a connected graph, a subset of vertices of least size whose deletion increases the number of connected components is the vertex connectivity of the graph. A graph with vertex connectivity κ is said to be κ-vertex connected. Given a k-vertex connected graph G, vertex connectivity augmentation determines a smallest set of edges whose augmentation to G makes it (κ + 1)-vertex connected. In this paper, we report our study of connectivity augmentation in 1-connected graphs, 2-connected graphs, and κ- trees. For a graph, our data structure maintains the set of equivalence classes based on an equivalence relation on the set of leaves of an associated tree. This partition determines a set of edges to be augmented to increase the connectivity of the graph by one. Based on our data structure we present a new combinatorial analysis and an elegant proof of correctness of our linear time algorithm for optimum connectivity augmentation. While this is the first attempt on the study of k-tree augmentation, the study on other two augmentations is reported in the literature. Compared to other augmentations reported in the literature, we avoid recomputation of the associated tree by maintaining the data structure under edge additions. Copyright © 2011, Australian Computer Society, Inc.
A Dirac-type characterization of k-chordal graphs
A graph is k-chordal if it has no induced cycle of length greater than k. We give a new characterization of k-chordal graphs that generalizes the well-known characterization of chordal graphs by Dirac in terms of simplicial vertices and simplicial orderings. © 2013 Elsevier B.V. All rights reserved.
Connected (s; t)-vertex separator parameterized by chordality
We investigate the complexity of _nding a minimum connected (s; t)-vertex separator ((s; t)-CVS) and present an interesting chordality di-chotomy: we show that (s; t)-CVS is NP-complete on graphs of chordal-ity at least 5 and present a polynomial-time algorithm for (s; t)-CVS on chordality 4 graphs. Further, we show that (s; t)-CVS is unlikely to have δlog2-∊n-approximation algorithm, for any ∊ > 0 and for some δ > 0, unless NP has quasi-polynomial Las Vegas algorithms. On the positive-side of approximation, we present a [c/2]-approximation algorithm for (s; t)-CVS on graphs with chordality c ≥ 3. Finally, in the parameterized setting, we show that (s; t)-CVS parameterized above the (s; t)-vertex connectivity is W[2]-hard.