Universität zu Köln

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

Preview

PDF Sep.pdf - Draft Version Download (198kB) | Preview

Abstract

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.

Item Type:	Journal Article
Creators:	Creators Email ORCID ORCID Put Code Schaudt, Oliver UNSPECIFIED UNSPECIFIED UNSPECIFIED Schrader, Rainer UNSPECIFIED UNSPECIFIED UNSPECIFIED Weil, Vera UNSPECIFIED UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-550335
Journal or Publication Title:	Discrete Mathematics
Volume:	313
Number:	6
Page Range:	pp. 809-820
Date:	2013
Publisher:	Elsevier
Language:	English
Faculty:	Faculty of Mathematics and Natural Sciences
Divisions:	Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects:	Data processing Computer science
Uncontrolled Keywords:	Keywords Language ARRAY(0x55e9335a3348) UNSPECIFIED
Refereed:	No
URI:	http://kups.ub.uni-koeln.de/id/eprint/55033