Paired-domination in claw-free graphs (Q2637727): 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/s00373-012-1224-5 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2031928820 / rank | |||
Normal rank |
Revision as of 20:52, 19 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Paired-domination in claw-free graphs |
scientific article |
Statements
Paired-domination in claw-free graphs (English)
0 references
14 February 2014
0 references
A paired-dominating set of a graph \(G\) is a dominating set \(S\) of vertices such that there exists a perfect matching in the subgraph induced by \(S\). The paired-domination number, denoted by \(\gamma_{pr}(G)\), is the minimum cardinality of a paired-dominating set in \(G\). The authors show that \(\gamma_{pr}(G) \leq (3n - 1)/5\) if \(G\) is a connected claw-free (i.e., \(K_{1,3}\)-free) graph of order \(n\) with minimum degree at least three. The bound is sharp. The authors also propose the following conjecture. If \(G\) is a connected claw-free graph of order \(n\) with minimum degree at least three, then \(\gamma_{pr}(G) \leq 4n/7\). This is a weaker form of a conjecture proposed by \textit{W. Goddard} and \textit{M. A. Henning} [Graphs Comb. 25, No. 5, 675--692 (2009; Zbl 1203.05117)] that asserts the same consequence for any connected graph \(G\), except the Petersen graph, of order \(n\) with minimum degree at least three.
0 references
paired-domination
0 references
claw-free graph
0 references
perfect matching
0 references