Graph vertices that always appear in smallest identifying codes studied
On the Vertices That Belong to All Minimum Identifying Codes
Discrete Mathematics
Summary
Some special sets of points in networks, called identifying codes, help uniquely recognize every point by looking at nearby points. The authors study points that must appear in every smallest such set, even if they don't have to be in all bigger sets. They found limits on how many such points can exist and showed that checking if a point has this property is a hard computational problem. They also describe certain graphs that closely reach these limits.
What this means in practice
- •For network designers: Understand which nodes must always be monitored to uniquely identify others in network fault diagnosis applications.
- •For security system architects: Determine critical sensor placements that appear in every minimal monitoring configuration for secure facility surveillance.
A theory result. No direct application yet.
Authors
Ville Junnila, Tero Laihonen, Havu Miikonen
Abstract
Identifying codes in graphs have been widely studied since their introduction by Karpovsky, Chakrabarty and Levitin in 1998. In this paper, we consider the vertices that are in every minimum identifying code in a graph. There are two types of such vertices: \emph{always-forced} vertices that belong to all identifying codes (minimum or not) and \emph{min-forced} vertices that belong to all minimum identifying codes. A vertex is called \emph{proper-min-forced} if it is min-forced but not always-forced. We show an upper bound $2n/3$ for the number of such proper-min-forced vertices in a closed-twin-free graph of order $n$. Moreover, for integers $n$ divisible by three, we construct an infinite family of graphs in which there are $2n/3-1$ such vertices. In addition, we determine the maximum number of edges in a graph of even order such that the graph contains proper-min-forced vertices. We also show that the decision problem of determining whether a given vertex in a graph is proper-min-forced is co-NP-hard.