On the structure of graphs with bounded asteroidal number (Q5943049): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set OpenAlex properties. |
||
(One intermediate revision by one other user not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/s003730170043 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W3022747647 / rank | |||
Normal rank |
Latest revision as of 01:56, 20 March 2024
scientific article; zbMATH DE number 1642137
Language | Label | Description | Also known as |
---|---|---|---|
English | On the structure of graphs with bounded asteroidal number |
scientific article; zbMATH DE number 1642137 |
Statements
On the structure of graphs with bounded asteroidal number (English)
0 references
14 July 2002
0 references
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\).
0 references
asteroidal set
0 references
asteroidal number
0 references
dominating target
0 references
dominating set
0 references