Author(s):
1. Yuya Kono:
Department of Mathematics, Western Michigan University,Kalamazoo, Michigan 49008-5248,USA
2. Ping Zhang:
Department of Mathematics, Western Michigan University,Kalamazoo, Michigan 49008-5248,USA
Abstract:
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.
Page(s):
10-15
Published:
Journal: Discrete Mathematics Letters, Volume: 8, Issue: 0, Year: 2022
Keywords:
distance
,
IDgraph
,
caterpillar
,
IDnumber
,
IDcoloring
References:
References are not available for this document.
Citations
Citations are not available for this document.