Delphi.science

On the Vertices That Belong to All Minimum Identifying Codes

Ville Junnila, Tero Laihonen, Havu Miikonen

arXivarxiv/2609.09851Sep 9, 2026math.COscore 0

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…

SourceJSON

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2609.09851
curl -X POST /api/v1/records/arxiv/2609.09851/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.09851/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'