Name
Abstract | ||
|---|---|---|
A red-white coloring of a nontrivial connected graph G 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, where d is the diameter of G and the ith coordinate of the code 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 problem of determining those graphs that are ID-graphs is investigated. The minimum number of red vertices among all ID-colorings of an ID-graph G is the identification number or ID-number of G and is denoted by ID(G). It is shown that (1) a nontrivial connected graph G has ID-number 1 if and only if G is a path, (2) the path of order 3 is the only connected graph of diameter 2 that is an ID-graph, and (3) every positive integer r different from 2 can be realized as the ID-number of some connected graph. The identification spectrum of an ID-graph G is the set of all positive integers r such that G has an ID-coloring with exactly r red vertices. Identification spectra are determined for paths and cycles. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1142/S0219265921500055 | JOURNAL OF INTERCONNECTION NETWORKS |
Keywords | DocType | Volume |
Distance, vertex identification, identification colorings | Journal | 21 |
Issue | ISSN | Citations |
01 | 0219-2659 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Gary Chartrand | 1 | 1 | 0.96 |
| Yuya Kono | 2 | 0 | 0.68 |
| Ping Zhang | 3 | 292 | 47.70 |