Perfection in Graphs, A New Look at Irredundance

Jason T. Hedetniemi1, Sandra M.Hedetniemi2, Stephen T.Hedetniemi3, Professor Emeritus3
1Department of Mathematical Sciences
2
3School of Computing Clemson University Clemson SC 29634

Abstract

Given a set \( S \subseteq V \) in a graph \( G = (V, E) \), we say that a vertex \( v \in V \) is perfect if \( |N[v] \cap S| = 1 \), that is, the closed neighborhood \( N[v] = \{v\} \cup \{u \mid uv \in E\} \) of \( v \) contains exactly one vertex in \( S \). A vertex \( v \) is almost perfect if it is either perfect or is adjacent to a perfect vertex. Similarly, we can say that a set \( S \subset V \) is (almost) perfect if every vertex \( v \in S \) is (almost) perfect; \( S \) is externally (almost) perfect if every vertex \( u \in V – S \) is (almost) perfect; and \( S \) is completely (almost) perfect if every vertex \( v \in V \) is (almost) perfect. In this paper, we relate these concepts of perfection to independent sets, dominating sets, efficient and perfect dominating sets, distance-2 dominating sets, and to perfect neighborhood sets in graphs. The concept of a set being almost perfect also provides an equivalent definition of irredundance in graphs.