The identification numbers of lollipop graphs
Gaixiang Cai, Fengru Xiao, Guidong Yu · AIMS Mathematics · 2025
A nontrivial connected graph $ G $ with diameter $ d $ can be assigned a red-white coloring, where the vertices of $ G $ are colored either red or white, with the stipulation that at least one vertex must be red. Associated with each vertex $ v $ of $ G $ is a $ d $-vector, called the code of $ v $, whose $ i $th coordinate is the number of red vertices at distance $ i $ from $ v $. A red-white coloring of $ G $ for which distinct vertices have distinct codes is called an identification coloring or $ ID $-coloring of $ G $. A graph $ G $ possessing an $ ID $-coloring is called an $ ID $-graph. The minimum number of red vertices among all $ ID $-colorings of an $ ID $-graph $ G $ is the identification number or $ ID $-number of $ G $. The number of red vertices in an identification coloring is called the identification coloring number. This article studied the identification coloring number of lollipop graphs by constructing vertex colorings.