Generalized power domination in claw-free regular graphs

DOI10.1007/S00373-022-02476-0MaRDI QIDQ2117535zbMATH OpenOpenAlexFDO

Authors Hangdi Chen, Qingjie Ye, Changhong Lu

Publication date 21 March 2022

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1905.11655

zbMATH Keywords

claw-free graphsdominationelectrical systems monitoringpower dominationregular graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Applications of graph theory (05C90) Graph theory (including graph drawing) in computer science (68R10) Programming involving graphs or networks (90C35)

Abstract: In this paper, we give a series of couterexamples to negate a conjecture and hence answer an open question on the $k$-power domination of regular graphs (see [P. Dorbec et al., SIAM J. Discrete Math., 27 (2013), pp. 1559-1574]). Furthermore, we focus on the study of $k$-power domination of claw-free graphs. We show that for $lin2,3$ and $kgel$, the $k$-power domination number of a connected claw-free $(k+l+1)$-regular graph on $n$ vertices is at most $fracnk+l+2$, and this bound is tight.

Recommendations

• Power domination in regular claw-free graphs
• Generalized power domination in regular graphs
• scientific article; zbMATH DE number 1472169
• Generalized power domination of graphs
• Clawfreeness of the powers of a graph
• Paired-domination in generalized claw-free graphs
• Power domination in the generalized Petersen graphs
• Upper total domination in claw‐free graphs
• Total restrained domination in claw-free graphs
• Domination versus edge domination on claw-free graphs

Cites work

• \(k\)-power domination in block graphs
• A note on power domination in grid graphs
• Approximation Algorithms and Hardness for Domination with Propagation
• Computing and Combinatorics
• Disproofs of three conjectures on the power domination of graphs
• Domination in Graphs Applied to Electric Power Networks
• Domination in graphs with bounded propagation: Algorithms, formulations and hardness results
• Generalized power domination in regular graphs
• Generalized power domination of graphs
• Generalized power domination: propagation radius and Sierpiński graphs
• scientific article; zbMATH DE number 1462928 (Why is no real title available?)
• Improved algorithms and complexity results for power domination in graphs
• Infectious power domination of hypergraphs
• Nordhaus-Gaddum problems for power domination
• On the \({k}\)-power domination of hypergraphs
• On the power domination number of the generalized Petersen graphs
• Parameterized power domination complexity
• Power domination in block graphs
• Power domination in graphs
• Power Domination in Product Graphs
• Power domination in regular claw-free graphs
• Restricted power domination and zero forcing problems
• The k-power domination problem in weighted trees
• The relationship between \(k\)-forcing and \(k\)-power domination

Cited in

(2)

• Disproofs of three conjectures on the power domination of graphs
• Power domination in regular claw-free graphs

This page was built for publication: Generalized power domination in claw-free regular graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2117535)