Article in press
Authors:
Title:
Recognizable coloring of graphs
PDFSource:
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:
- 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 - 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 - F. Harary and M. Plantholt, The point-distinguishing chromatic index, in: Graphs and Applications, (Wiley, New York 1985) 147–162.
- 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 - 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 - 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 - M. Radcliffe and P. Zhang, Irregular colorings of graphs, Bull. Inst. Combin. Appl. 49 (2007) 41–59.
Close