DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2023): 0.5

5-year Journal Impact Factor (2023): 0.6

CiteScore (2023): 2.2

SNIP (2023): 0.681

Discussiones Mathematicae Graph Theory

Article in press


Authors:

Z. Hamed-Labbafian

Zahra Hamed-Labbafian

Ferdowsi University of Mashhad

email: Zaharahamed444@gmail.com

M.A. Henning

Michael A. Henning

University of Johannesburg

email: mahenning@uj.ac.za

0000-0001-8185-067X

M. Tavakoli

Mostafa Tavakoli

ferdowsi university of mashhad

email: m_tavakoli@um.ac.ir

N. ‎‎Sabeghi

Narjes ‎‎Sabeghi

‎Velayat University

email: sabeghinarjes@gmail.com

Title:

Recognizable coloring of graphs

PDF

Source:

Discussiones Mathematicae Graph Theory

Received: 2024-04-05 , Revised: 2024-12-10 , Accepted: 2024-12-10 , Available online: 2025-01-14 , https://doi.org/10.7151/dmgt.2574

Abstract:

Let $G$ be a connected graph and $f$ be a mapping from $V(G)$ to $S$, where $S$ is a set of $k$ colors for some positive integer $k$. The color code of a vertex $v$ of $G$ with respect to $f$, denoted by code$_G(v|f)$, is the ordered $(k+1)$-tuple $(x_0, x_1,\ldots, x_k)$ where $x_0$ is the color assigned to $v$ and where $x_i$ is the number of vertices adjacent to $v$ of color $i$ for $1 \le i \le k$, that is, $x_i = |\{uv\in E(G) \colon f(u)=i\}|$ for $1 \le i \le k$. The mapping $f$ is a recognizable coloring if code$_G(u|f) \ne$ code$_G(v|f)$ for every two distinct vertices $u$ and $v$ of $G$. The minimum number of colors needed for a recognizable coloring of $G$ is the recognition number of $G$ denoted by rn$(G)$. Our goal in this article is to give the exact value of the recognition number of the corona product $G \circ H$ of two graphs $G$ and $H$ for the cases $H=K_n$ and $n \ge |V(G)|$, or $G=K_m$ and $H=K_n$ with $m>n$. In addition, we obtain the exact value of the recognition number of the edge corona product $G \diamond H$ of $G$ and $H$ for the case that $G$ is a non-trivial graph with minimum degree at least $2$ and $H = K_n$ where $n \ge |E(G)|$. Moreover, an algorithm for computing the recognition number of graphs is presented. As an application of our algorithm, we compute the recognition number of some fullerene graphs.

Keywords:

recognizable coloring, corona product, local search algorithm, fullerene

References:

  1. G. Chartrand, L. Lesniak, D.W. VanderJagt and P. Zhang, Recognizable colorings of graphs, Discuss. Math. Graph Theory 28 (2008) 35–57.
    https://doi.org/10.7151/dmgt.1390
  2. M.J. Dorfling and S. Dorfling, Recognizable colorings of cycles and trees, Discuss. Math. Graph Theory 32 (2012) 81–90.
    https://doi.org/10.7151/dmgt.1587
  3. F. Harary and M. Plantholt, The point-distinguishing chromatic index, in: Graphs and Applications, (Wiley, New York 1985) 147–162.
  4. T.W. Haynes, S.T. Hedetniemi and M.A. Henning, Domination in Graphs: Core Concepts, Springer Monogr. Math. (Springer, Cham, 2023).
    https://doi.org/10.1007/978-3-031-09496-5
  5. Y. Hou and W.-C. Shiu, The spectrum of the edge corona of two graphs, Electron. J. Linear Alg. 20 (2010) 586–594.
    https://doi.org/10.13001/1081-3810.1395
  6. S. Klavžar and M. Tavakoli, Dominated and dominator colorings over $($edge$)$ corona and hierarchical products, Appl. Math. Comput. 390 (2021) 125647.
    https://doi.org/10.1016/j.amc.2020.125647
  7. M. Radcliffe and P. Zhang, Irregular colorings of graphs, Bull. Inst. Combin. Appl. 49 (2007) 41–59.

Close