On the Vertices That Belong to All Minimum Identifying Codes

1 Introduction

• An identifying code gives every vertex a nonempty, distinct set of codewords in its closed neighbourhood; minimizing the code corresponds to minimizing sensors in a network.The introduction describes sensors as monitoring closed neighbourhoods and reporting whether the sought object is present.Source: §1 · p. 2
• In a connected, nontrivial closed-twin-free graph, a vertex is always-forced exactly when some pair’s closed neighbourhoods differ only by that vertex.More generally, testing whether deleting a vertex leaves an identifying code determines whether it is always-forced.Source: §1 · p. 2
• A graph of order n can have n−1 always-forced vertices: this is attained by a complete graph of odd order after removing a maximal matching.The remaining universal vertex is excluded from the always-forced set.Source: §1 · pp. 2–3
• A proper-min-forced vertex belongs to every minimum identifying code but is not always-forced, so it must be chosen in a minimum code without belonging to every code.The paper focuses on these vertices because always-forced vertices are already in every minimum code.Source: §1 · p. 3
• The paper previews a 2n/3 upper bound, a tight even-order edge bound, and co-NP-hardness for deciding whether a vertex is proper-min-forced.It also announces an infinite family with 2n/3−1 such vertices when n is divisible by three.Source: §1 · p. 3

2 On the maximum number of proper-min-forced vertices

• The proof encodes codeword distinctions in a bipartite colour graph, where each proper-min-forced codeword labels at least two edges.This edge requirement supports selecting two edges for each proper-min-forced vertex in the upper-bound argument.Source: §2 · pp. 3–5
• pf(G)/2 + γID(G) ≤ n, so every connected, nontrivial, closed-twin-free graph has at most 2n/3 proper-min-forced vertices.The inequality implies pf(G) ≤ 2n/3.Source: §2 · p. 7
• For n ≥ 9 divisible by three, an infinite family has 2n/3 − 1 proper-min-forced vertices, one fewer than the upper bound.In the construction, γID(Gk) = 2k + 3, and the specified minimum code has all its vertices min-forced.Source: §2 · p. 8

• 2k + 3 = 2n/3 − 1 proper-min-forced vertices occur in Gk for n = 3k + 6 and k ≥ 1, nearly attaining Theorem 13’s 2n/3 upper bound.Source: §2 · p. 8
• S′ is an ID code of size 2k + 4 that omits min-forced xi, v1, v2, v5, and yi; unlike these vertices, P3’s 2n/3 min-forced endpoints are always-forced.Source: §2 · p. 8

3 An optimal result for dense graphs with proper-min-forced vertices

• For even order, the section determines a tight maximum-edge bound for graphs containing proper-min-forced vertices.The supplied passages establish tightness but do not give the complete numerical bound.Source: §3 · pp. 9–10
• In the complement-based family, every identifying code contains at least 2m−1 vertices from X∪Y; with a universal vertex, it contains all of X∪Y.The first condition is stated for an identifying code in the lemma; the second follows from its universal-vertex case.Source: §3 · p. 9
• In G2k, built from the complement of a bull, an isolated vertex, and k−3 disjoint edges, v1 is proper-min-forced.The code A ∪ {v1} is the unique minimum identifying code, while deleting v1 from the full vertex set still gives an identifying code.Source: §3 · pp. 9–10
• For n=2k with k≥6, Theorem 16 rules out proper-min-forced vertices above its stated edge threshold.The provided theorem text does not include the complete numerical threshold.Source: §3 · p. 10
• K2k with a perfect matching removed has no proper-min-forced vertices because each vertex can be omitted by a minimum identifying code.Its smallest identifying codes are V(G)\{v} for any vertex v.Source: §3 · p. 10
• The complement constructions based on C3 and P5 yield no proper-min-forced vertices, despite their different minimum-code structures.For the C3 case, the vertices in X∪Y are always-forced; for the P5 case, several minimum identifying codes omit different vertices.Source: §3 · p. 11

4 On computational complexity

• Deciding whether a given vertex is proper-min-forced is co-NP-hard, via a polynomial-time reduction from 3-SAT.The reduction makes w proper-min-forced if and only if the 3-SAT instance is not satisfiable.Source: §4 · pp. 12–13
• The reduction builds variable and clause gadgets, together with vertices w and v, into a graph with 6n + 2m + 2 vertices and 6n + 5m + 1 edges.Each variable gadget has six vertices; each clause gadget has two.Source: §4 · p. 12
• The constructed graph has identifying number 3n + m + 1, established by a lower bound for identifying codes and a code of that size.The lower bound counts contributions from variable gadgets, clause gadgets, and the pair {w, v}; the exhibited code supplies the matching upper bound.Source: §4 · pp. 12–13
• The vertex w is not always-forced because deleting it from V(G) still leaves an identifying code.The proof checks that the resulting I-sets remain nonempty and distinct.Source: §4 · p. 13
• If the 3-SAT instance is satisfiable, its truth assignment yields a minimum identifying code that omits w.The constructed code has 3n + m + 1 vertices, the identifying number of the graph.Source: §4 · p. 13
• Conversely, a minimum identifying code omitting w yields a satisfying assignment by selecting one literal per variable and a true literal in every clause.The clause condition follows because the code must distinguish each pair αj, βj.Source: §4 · p. 13

5 Conclusions

• The number of proper-min-forced vertices is at most 2n/3, and an infinite family attains 2n/3 − 1 when n is divisible by three.Whether 2n/3 − 1 or 2n/3 is the optimal bound remains open.Source: §5 · p. 13
• For even-order graphs containing proper-min-forced vertices, the paper gives an upper bound on the number of edges and shows that it is attainable.The passage does not state the bound's value.Source: §5 · p. 14
• Deciding whether a vertex is proper-min-forced is co-NP-hard, whereas deciding whether it is always-forced is algorithmically easy.Source: §5 · p. 14