On the separability of graphs

Schaudt, Oliver and Schrader, Rainer and Weil, Vera (2013) On the separability of graphs.
Published in: Discrete Mathematics Vol. 313 (6). pp. 809-820.


Recently, Cicalese and Milanič introduced a graph-theoretic concept called separability. A graph is said to be k-separable if any two non-adjacent vertices can be separated by the removal of at most k vertices. The separability of a graph G is the least k for which G is k-separable. In this paper, we investigate this concept under the following three aspects. First, we characterize the graphs for which in any non-complete connected induced subgraph the connectivity equals the separability, so-called separability-perfect graphs. We list the minimal forbidden induced subgraphs of this condition and derive a complete description of the separability-perfect graphs.We then turn our attention to graphs for which the separability is given locally by the maximum intersection of the neighborhoods of any two non-adjacent vertices. We prove that all (house,hole)-free graphs fulfill this property – a class properly including the chordal graphs and the distance-hereditary graphs. We conclude that the separability can be computed in O(m∆) time for such graphs.In the last part we introduce the concept of edge-separability, in analogy to edge-connectivity, and prove that the class of k-edge-separable graphs is closed under topological minors for any k. We explicitly give the forbidden topological minors of the k-edge-separable graphs for each 0 ≤ k ≤ 3.

Download: [img] PDF - Submitted Version
Download (198kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
Depositing User: Rainer Schrader
Date Deposited: 04 Dec 2012 13:37
Last Modified: 08 Jul 2013 09:55
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/687