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

Le résumé fourni par la source

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.

Ce résumé expose les affirmations des auteurs. BNTIC ne l’interprète pas comme une validation indépendante des résultats.