Generalized power domination in claw-free regular graphs

DOI10.1007/S00373-022-02476-0zbMATH Open1485.05133arXiv1905.11655OpenAlexW3094266530MaRDI QIDQ2117535FDOQ2117535

Changhong Lu, Hangdi Chen, Qingjie Ye

Publication date: 21 March 2022

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

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.

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

zbMATH Keywords

dominationregular graphsclaw-free graphspower dominationelectrical systems monitoring

Mathematics Subject Classification ID

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

Cites Work

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

Recommendations

• Title not available (Why is that?) 👍 👎
• Upper total domination in claw‐free graphs 👍 👎
• Generalized power domination of graphs 👍 👎
• Paired-domination in generalized claw-free graphs 👍 👎
• Total restrained domination in claw-free graphs 👍 👎
• Clawfreeness of the powers of a graph 👍 👎
• Generalized power domination in regular graphs 👍 👎
• Power domination in regular claw-free graphs 👍 👎
• Power domination in the generalized Petersen graphs 👍 👎
• Domination versus edge domination on 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)