A note on the identification numbers of caterpillars
Yuya Kono, Ping Zhang · Discrete Mathematics Letters · 2021
A red-white coloring of a nontrivial connected graph G of diameter d is an assignment of red and white colors to the vertices of G where at least one vertex is colored red.Associated with each vertex v of G is a d-vector, called the code of v, whose ith 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 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.A caterpillar is a tree of order 3 or more, the removal of whose leaves produces a path.A caterpillar possessing an ID-coloring is an ID-caterpillar.In this note, we characterize all ID-caterpillars, determine all possible values of the ID-numbers of ID-caterpillars, and show that each value is realizable.