On the Structure of Graphs with Bounded Asteroidal Number |
| |
Authors: | Ton Kloks Dieter Kratsch Haiko Müller |
| |
Affiliation: | Department of Mathematics and Computer Science, Vrije Universiteit, De Boelelaan 1081A, 1081 HV Amsterdam, The Netherlands. e-mail: kloks@cs.vu.nl, NL Fakult?t für Mathematik und Informatik, Friedrich-Schiller-Universit?t Jena, 07740 Jena, Germany. e-mail: kratsch@minet.uni-jena.de, DE Fakult?t für Mathematik und Informatik, Friedrich-Schiller-Universit?t Jena, 07740 Jena, Germany. e-mail: hm@minet.uni-jena.de, DE
|
| |
Abstract: | A set A⊆V of the vertices of a graph G=(V,E) is an asteroidal set if for each vertex a∈A, the set A{a} is contained in one component of G−N[a]. The maximum cardinality of an asteroidal set of G, denoted by an (G), is said to be the asteroidal number of G. We investigate structural properties of graphs of bounded asteroidal number. For every k≥1, an (G)≤k if and only if an (H)≤k for every minimal triangulation H of G. A dominating target is a set D of vertices such that D∪S is a dominating set of G for every set S such that G[D∪S] is connected. We show that every graph G has a dominating target with at most an (G) vertices. Finally, a connected graph G has a spanning tree T such that d T (x,y)−d G (x,y)≤3·|D|−1 for every pair x,y of vertices and every dominating target D of G. Received: July 3, 1998 Final version received: August 10, 1999 |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|