Distance-dominating cycles in quasi claw-free graphs (Q1808712): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/s003730050061 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2022510626 / rank | |||
Normal rank |
Latest revision as of 01:39, 20 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Distance-dominating cycles in quasi claw-free graphs |
scientific article |
Statements
Distance-dominating cycles in quasi claw-free graphs (English)
0 references
10 April 2000
0 references
The paper concerns quasi claw-free graphs. For a vertex \(u\) of a graph \(G\) the symbol \(N(u)\) denotes the open neighbourhood of \(u\) in \(G\), i.e. the set consisting of all vertices which are adjacent to \(u\) in \(G\). The closed neighbourhood of \(u\) is \(N[u]= N(u)\cup \{u\}\). If for any two vertices \(a_1\), \(a_2\) having distance 2 in \(G\) there exists at least one vertex \(u\in N(a_1)\cap N(a_2)\) such that \(N[u]\subseteq N[a_1]\cup N[a_2]\), then \(G\) is called quasi claw-free. The paper studies connectivity and dominance in such graphs. A cycle \(C\) is \(m\)-dominating in \(G\), if for each vertex of \(G\) there exists a vertex of \(C\) having distance at most \(m\) from it. The main result states that if a quasi claw-free graph \(G\) is \(\kappa\)-connected for \(\kappa\geq 2\) and \(m\) is a nonnegative integer, then either \(G\) has an \(m\)-dominating cycle, or \(G\) has a set of at least \(\kappa+ 1\) vertices such that the distance between every pair of them is at least \(2m+3\).
0 references
quasi claw-free graphs
0 references
distance
0 references
connectivity
0 references
dominance
0 references
cycle
0 references