No Detail Found!

A note on the identification numbers of caterpillars

Author(s)
Yuya Kono Department of Mathematics, Western Michigan University,Kalamazoo, Michigan 49008-5248,USA
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.
Publication Details
Page(s) 10-15
Published Journal: Discrete Mathematics Letters, Volume: 8, Issue: 0, Year: 2022

Request the full text from PASTIC

Keywords
distance, ID-graph, caterpillar, ID-number, ID-coloring
0

Citations

0

Downloads

209

Views