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. 809820.
Abstract
Recently, Cicalese and Milanič introduced a graphtheoretic concept called separability. A graph is said to be kseparable if any two nonadjacent 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 kseparable. In this paper, we investigate this concept under the following three aspects. First, we characterize the graphs for which in any noncomplete connected induced subgraph the connectivity equals the separability, socalled separabilityperfect graphs. We list the minimal forbidden induced subgraphs of this condition and derive a complete description of the separabilityperfect 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 nonadjacent vertices. We prove that all (house,hole)free graphs fulfill this property – a class properly including the chordal graphs and the distancehereditary 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 edgeseparability, in analogy to edgeconnectivity, and prove that the class of kedgeseparable graphs is closed under topological minors for any k. We explicitly give the forbidden topological minors of the kedgeseparable graphs for each 0 ≤ k ≤ 3.
Download: 
PDF
 Submitted Version
Download (193Kb)  Preview 

Export as:  
Editorial actions:  View Item (Login required) 
Item Type:  Article 

Citations:  No citation data. 
Uncontrolled Keywords:  separability connectivity HHfree graphs forbidden topological minors 
Subjects: 

Divisions:  Institute of Computer Science > Computer Science Department  Prof. Dr. Schrader 
Related URLs: 
ZAIK Number:  UNSPECIFIED 

Depositing User:  Rainer Schrader 
Date Deposited:  04 Dec 2012 13:37 
Last Modified:  08 Jul 2013 09:55 
URI:  http://earchive.informatik.unikoeln.de/id/eprint/687 