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

Institutions

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
article

Optimal vertex set partitions into different closed neighborhoods in powers of graphs and their complements

Chandru Hegde, N. Kavitha, K. Karthik
Asian-European Journal of Mathematics
Advanced Graph Theory Research
article

Optimal vertex set partitions into different closed neighborhoods in powers of graphs and their complements

Chandru Hegde, N. Kavitha, K. Karthik
article en

Abstract

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.

Asian-European Journal of MathematicsVol. 18(12)
Mangalore University (IN), Government of Karnataka (IN)
Openalex Percentile: Top 84%
Advanced Graph Theory Research
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.