Longest cycles in almost claw-free graphs (Q1576574): Difference between revisions
From MaRDI portal
Created a new Item |
Set OpenAlex properties. |
||
(4 intermediate revisions by 3 users not shown) | |||
Property / author | |||
Property / author: Q591118 / rank | |||
Property / author | |||
Property / author: Ming-Chu Li / rank | |||
Normal rank | |||
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/s003730070024 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2040573390 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 01:58, 20 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Longest cycles in almost claw-free graphs |
scientific article |
Statements
Longest cycles in almost claw-free graphs (English)
0 references
21 January 2001
0 references
A claw of a (finite, undirected) graph \(G\) is an induced subgraph isomorphic with \(K_{1,3}\). It is said that \(G\) is almost claw-free if the domination number of the neighbourhood of each vertex is at most 2 and besides the centers of all claws of \(G\) form an independent set. Letting \(\delta\) denote the minimum degree of \(G\), the author establishes the following theorems. (1) Every 2-connected almost claw-free graph on \(n\) vertices contains a cycle of length at least \(\min\{n,2\delta+ 4\}\) and the bound \(2\delta+ 4\) is the best possible. (2) Every 3-connected almost claw-free graph on \(n\) vertices contains a cycle of length at least \(\min\{n, 4\delta\}\). It is noted that (1) generalizes a result of \textit{M. M. Matthews} and \textit{D. P. Sumner} [J. Graph Theory 9, 269-277 (1985; Zbl 0591.05041)] on claw-free graphs, while (2) improves one of the author.
0 references
claw
0 references
domination number
0 references
independent set
0 references
claw-free graph
0 references
cycle
0 references