2021/08/15 by Ganesan, Ghurumuruhan
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2108.06733
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~\(uv ∈ \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.