Vertex identification in trees

Yuya Kono; Ping Zhang

doi:10.47443/dml.2021.0042

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. Necessary conditions are established for those trees that are ID-graphs. A tree T is starlike if T is obtained by subdividing the edges of a star of order 4 or more. It is shown that for every positive integer r different from 2, there exist starlike trees satisfying some prescribed properties having ID-number r.

Publication Details

Page(s) 66-73

DOI 10.47443/dml.2021.0042

Published Journal: Discrete Mathematics Letters, Volume: 7, Issue: 0, Year: 2021

Request the full text from PASTIC

Keywords

tree, vertex identification, Distance, identification coloring

References

. .. 1 and 1, : .

Ali A. .2020 .A survey of antiregular graphs. Contrib. Math. 1, : 67-79.

Ali A.,Zhang P. .2021 .. , : .

Chappell G. G.,Gimbel J.,Hartman C. .2008 .Bounds on the metric and partition dimensions of a graph. Ars Combin, 88 : 349-366.

Chartrand G.,Eroh L.,Johnson M. A.,Oellermann O. R. .2000 .Resolvability in graphs and the metric dimension of a graph, Discrete Appl. , 105 : 99-113.

Chartrand G.,Kono Y.,P. Zhang, Y. . .Distance vertex identification in graphs. J. Interconnection Netw, 21(2021) : 2150005.

Chartrand G.,P. Zhang, G. .2000 .The partition dimension of a graph. Aequationes Math, 59 : 45-54.

Chartrand G.,P. Zhang, G. .2003 .The theory and applications of resolvability in graphs - a survey, Congr. , 160 : 47-68.

Foucaud F.,Mertzios G. B.,Naserasr R.,Parreau A.,Valicov P. .2017 .-domination and metric dimension on interval and permutation graphs. I. Bounds, Theoret. Comput. Sci, 68 : 43-58.

Foucaud F.,Mertzios G. B.,Naserasr R.,Parreau A.,Valicov P. .2017 .-domination and metric dimension on interval and permutation graphs. II. Algorithms and complexity. Algorithmica, 78 : 914-944.

Harary F.,Melter R. A. .1976 .On the metric dimension of a graph. Ars Combin, 2 : 191-195.

Hauptmann M.,Schmied R.,Viehmann C. .2012 .Approximation complexity of metric dimension problem. J. Discrete Algorithms, 14 : 214-222.

Hernando C.,Mora M.,Pelayo M. I.,Seara C.,Wood D.,David R. . .Extremal graph theory for metric dimension and diameter. Electron. J. Combin, 17(2010) : R30.

Johnson M. A. .1993 .Structure-activity maps for visualizing the graph variables arising in drug design. J. Biopharm. Statist, 3 : 203-236.

Johnson M. A.,Carbo M. A.,Stamford M. A. .1998 .Browsable structure-activity datasets. Advances in Molecular Similarity, 2 : 153-170.

Slater P. J. .1975 .. Congr. Numer, 14 : 549-559.

Slater P. J. .1988 .Dominating and reference sets in graphs. J. Math. Phys. Sci, 22 : 445-455.

Zhang P.,Color-Induced Graph Colorings .2015 .. , : .

Zhang P. .2016 .. , : .