Strong identification codes for graphs

DOI10.1016/J.DISC.2021.112475MaRDI QIDQ2037550zbMATH OpenOpenAlexFDO

Authors Ghurumuruhan Ganesan

Publication date 8 July 2021

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2108.06733

zbMATH Keywords

probabilistic methodstrong identification codesstrong neighbourhood graphs

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Combinatorial codes (94B25) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Abstract: For any graph~(G,) a set of vertices~({cal V}) is said to be dominating if every vertex of~(G) contains at least one node of~(G) and separating if each vertex~(v) contains a unique neighbour~(u_v in {cal V}) that is adjacent to no other vertex of~(G.) If~({cal V}) is both dominating and separating, then~({cal V}) is defined to be an identification code. In this paper, we study strong identification codes with an index~(r,) by imposing the constraint that each vertex of~(G) contains at least~(r) unique neighbours in~({cal V}.) We use the probabilistic method to study both the minimum size of strong identification codes and the existence of graphs that allow an identification code with a given index.

Recommendations

• Extremal graphs for the identifying code problem
• Extremal cardinalities for identifying and locating-dominating codes in graphs
• The compared costs of domination location-domination and identification
• Locating-dominating sets and identifying codes in graphs of girth at least 5
• Identifying and locating-dominating codes on chains and cycles

Cites work

• Bounds for identifying codes in terms of degree parameters
• Characterizing identifying codes from the spectrum of a graph or digraph
• On a new class of codes for identifying vertices in graphs
• On graphs having a \(V\setminus \{x\}\) set as an identifying code
• On the size of identifying codes in triangle-free graphs
• Paths in graphs
• The probabilistic method. With an appendix on the life and work of Paul Erdős.

Cited in

(3)

• Codes for strong identification
• Some links between identifying codes and separating, dominating and total dominating sets in graphs
• Watching systems in graphs: an extension of identifying codes

This page was built for publication: Strong identification codes for graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2037550)