Optimal vertex set partitions into different closed neighborhoods in powers of graphs and their complements
In a graph [Formula: see text], a subset [Formula: see text] is called an efficient dominating set if every vertex in [Formula: see text] is dominated by exactly one vertex in [Formula: see text]. A vertex [Formula: see text] is said to be dominated by a vertex in [Formula: see text] if it either belongs to [Formula: see text] or is adjacent to a vertex in [Formula: see text]. Generalizing this notion, a [Formula: see text]-efficient dominating set is defined via partitions of the vertex set into closed [Formula: see text]-neighborhoods for [Formula: see text]. The minimum cardinality of such a set is called the [Formula: see text]-efficient domination number of [Formula: see text], denoted [Formula: see text]. In this paper, we focus on determining [Formula: see text], the 1-efficient domination number of the [Formula: see text]th power of a graph [Formula: see text], and its complement [Formula: see text]. We characterize graphs for which [Formula: see text], and compute exact values of [Formula: see text] for powers of paths, cycles, and their complements. Our results provide structural insights into neighborhood-based vertex partitions and efficient domination in graph powers.
Authors
- Chandru Hegde
- N. Kavitha
- K. Karthik
Institutions
- Mangalore University (IN)
- Government of Karnataka (IN)
Publication Details
- Journal
- Asian-European Journal of Mathematics
- Published
- 2025-06-20
- DOI
- https://doi.org/10.1142/s1793557125500664
- Primary Topic
- Advanced Graph Theory Research
- Type
- article
- Field-Weighted Citation Impact
- 0.00