Forbidden subgraphs and prohibited colorings for vertex identification in graphs

Title

Forbidden subgraphs and prohibited colorings for vertex identification in graphs

Creator

Iyer, Akshay Vishnuprakash; Kureethara, Joseph Varghese

Description

A red-white coloring of a graph G of diameter d is done by assigning the colors red and white to the vertices of the graph such that, there should be at least one red vertex. Then, each of the vertices is assigned a vector of length d called code in which the value of ith coordinate is equal to the number of red-colored vertices at distance i from this vertex, i ? {1, 2, 3,,d}. A red-white coloring when the code assigned to each vertex is different than that coloring is called an ID-coloring and a graph which has an ID-coloring is an ID-graph. The minimum number of vertices required to be colored red to get an ID-coloring is called the ID-number. ID-coloring is not possible for all graphs. There exist many properties which prevent ID-coloring. In this paper, we explore some forbidden induced subgraphs and certain prohibited red-white colorings which prevent the existence of ID-coloring. 2025 World Scientific Publishing Company.

Source

Discrete Mathematics, Algorithms and Applications;Issue;;Article No.;2550092;

Date

01-01-2025

Publisher

World Scientific

Subject

distance; Graph coloring; ID-coloring; ID-graph

Coverage

Iyer A.V., Department of Mathematics, CHRIST (Deemed to be University), Karnataka, Bengaluru, 560029, India; Kureethara J.V., Department of Mathematics, CHRIST (Deemed to be University), Karnataka, Bengaluru, 560029, India

Rights

Restricted Access; Hardcopy may be available in the library

Relation

ISSN: 17938309;

Format

online

Language

English

Type

Article

Identifier

https://doi.org/10.1142/S1793830925500922

https://www.scopus.com/pages/publications/105007645398?origin=resultslist