Distance-dominating cycles in quasi claw-free graphs
type: Item
instance of: scholarly article
title: Distance-dominating cycles in quasi claw-free graphs
zbMATH Open document ID: 0934.05097
author: Ciping Chen
author: Amel Harkat-Benhamdine
author: Hao Li
published in: Graphs and Combinatorics
publication date: 2000-04-10T00:00:00Z
review text: 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\).
reviewed by: Bohdan Zelinka
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C12
zbMATH DE Number: 1369701
zbMATH Keywords: quasi claw-free graphs
zbMATH Keywords: distance
zbMATH Keywords: connectivity
zbMATH Keywords: dominance
zbMATH Keywords: cycle
MaRDI profile type: Publication
full work available at URL: s003730050061
OpenAlex ID: W2022510626
DOI: 10.1007/S003730050061
description: scientific article; zbMATH DE number 1369701