Generalized power domination in claw-free regular graphs

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

Authors: Hangdi Chen, Qingjie Ye, Changhong Lu 

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

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

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?)
• 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
• 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 Product Graphs
• Power domination in block graphs
• Power domination in 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
• \(k\)-power domination in block graphs

Cited In (2)

• Power domination in regular claw-free graphs
• Disproofs of three conjectures on the power domination of 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)