On the Vertices That Belong to All Minimum Identifying Codes
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.
Related
- Vertices that belong to every minimum dominating set of a graph and their connection with transportation sharing systems with study cases in Campo de Gibraltar area
- The minimum number of vertices of a triangulation of ℝℙ5
- New Minimum Storage Regenerating Codes With Small Sub-packetization Levels for All Admissible Repair Degrees
- CPM-LDPC Codes Attaining the Minimum-Distance Bound
- Convolutional Codes from Cyclic Codes with Guaranteed Free and Local Minimum Distances
BibTeX
@misc{junnila2026vertices,
title = {{On the Vertices That Belong to All Minimum Identifying Codes}},
author = {Ville Junnila and Tero Laihonen and Havu Miikonen},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.09851},
eprint = {2609.09851},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.09851},
}
RIS
TY - UNPB
TI - On the Vertices That Belong to All Minimum Identifying Codes
AU - Ville Junnila
AU - Tero Laihonen
AU - Havu Miikonen
PY - 2026
DA - 2026/09/09
PB - arXiv
DO - 10.48550/arxiv.2609.09851
UR - https://arxiv.org/abs/2609.09851
AB - 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.
ER -