The Extended Dominating Sets in Graphs

Zhipeng Gao (), Yongtang Shi (), Changqing Xi and Jun Yue ()
Additional contact information
Zhipeng Gao: Center for Combinatorics and LPMC, Nankai University, Tianjin 300071, P. R. China
Yongtang Shi: Center for Combinatorics and LPMC, Nankai University, Tianjin 300071, P. R. China
Changqing Xi: Center for Combinatorics and LPMC, Nankai University, Tianjin 300071, P. R. China
Jun Yue: School of Mathematics Science, Tiangong University, Tianjin 300387, P. R. China

Asia-Pacific Journal of Operational Research (APJOR), 2023, vol. 40, issue 05, 1-20

Abstract: Let G = (V (G),E(G)) be a graph and let k be an integer. A vertex subset S ⊆ V (G) is called a k-extended dominating set if every vertex u of G satisfies one of the following conditions: the distance between u and S is at most one or there are at least k different vertices s1,s2,…,sk ∈ S such that the distance between u and si (i ∈ [k]) is two. The k-extended domination number γek(G) of G is the minimum size over all k-extended dominating sets in G. When k = 2, they are called the extended dominating set and the extended domination number of G, respectively. In this paper, we mainly study the bounds of the extended domination numbers of graphs. First, we obtain the exact values of the extended domination numbers for paths and cycles. And then the Nordhaus–Gaddum bounds for the extended domination numbers are provided. Additionally, we give some bounds of the extended domination numbers for planar graphs with small diameters. Finally, we consider the k-extended domination numbers in Random graphs.

Keywords: Domination; extended domination; planar graph; random graph (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595923400158
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:apjorx:v:40:y:2023:i:05:n:s0217595923400158

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595923400158

Access Statistics for this article

Asia-Pacific Journal of Operational Research (APJOR) is currently edited by Gongyun Zhao

More articles in Asia-Pacific Journal of Operational Research (APJOR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().