Locally well-dominated and locally independent well-dominated graphs

Zverovich, Igor; Zverovich, Vadim

Abstract

In this article we present characterizations of locally well-dominated graphs and locally independent well-dominated graphs, and a sufficient condition for a graph to be k-locally independent well-dominated. Using these results we show that the irredundance number, the domination number and the independent domination number can be computed in polynomial time within several classes of graphs, e.g., the class of locally well-dominated graphs.

Citation

Zverovich, I., & Zverovich, V. (2003). Locally well-dominated and locally independent well-dominated graphs. Graphs and Combinatorics, 19(2), 279-288. https://doi.org/10.1007/s00373-002-0507-7

• Journal Article Type: Article
• Publication Date: Jun 1, 2003
• Journal: Graphs and Combinatorics
• Print ISSN: 0911-0119
• Publisher: Springer Verlag
• Peer Reviewed: Peer Reviewed
• Volume: 19
• Issue: 2
• Pages: 279-288
• DOI: https://doi.org/10.1007/s00373-002-0507-7
• Keywords: locally well-dominated graphs, irredundance number, domination number, independent domination number
• Public URL: https://uwe-repository.worktribe.com/output/1069922
• Publisher URL: http://dx.doi.org/10.1007/s00373-002-0507-7