# zbMATH — the first resource for mathematics

On the structure of graphs with bounded asteroidal number. (English) Zbl 0989.05059
Let $$G = (V, E)$$ be a graph and $$A \subseteq V$$. Then $$A$$ is said to be an asteroidal set if for each $$a \in A$$, the vertices in $$A- \{a\}$$ are pairwise connected in $$G-N[a]$$. The maximum cardinality of an asteroidal set of $$G$$, denoted by $$\text{an}(G)$$, is called the asteroidal number of $$G$$. An asteroidal set with three vertices is called an asteroidal triple. Structural properties of graphs without asteroidal triples have been studied extensively. It is shown, in this article, that for $$k \geq 1$$, $$\text{an}(G) \leq k$$ if and only if $$\text{an}(H) \leq k$$ for every minimal triangulation $$H$$ of $$G$$. A dominating target is a set $$D$$ of vertices such that $$D \cup S$$ is a dominating set for every set $$S$$ such that $$G[D \cup S]$$ is connected. It is shown that every graph has a dominating target with at most $$\text{an}(G)$$ vertices. This extends a result of Corneil, Olariu and Stewart which states that every asteroidal triple free connected graph contains a pair of vertices that form a dominating target set. In the concluding section of the paper it is shown that there is a tree $$T$$ in $$G$$ with $$d_T(x, y) - d_G(x, y) \leq 3 \cdot |D|-1$$ for every pair $$x, y$$ of vertices and every dominating target $$D$$ of $$G$$.

##### MSC:
 05C35 Extremal problems in graph theory 05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
Full Text: