On the structure of graphs with bounded asteroidal number (Q5943049)

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\).