Injective (edge) colorings of generalized Sierpiński graphs

Abstract

Generalized Sierpiński graphs constitute a distinctive class of fractal-like networks with recursive definition: given a graph $G$, $S_G^1=G$ while $S_G^n$ is obtained from $|V(G)|$ copies of $S_G^{n-1}$ by adding some edges in a prescribed way that reflects the structure of $G$. Many graph invariants have been studied in generalized Sierpiński graphs. In this paper, we focus on their injective colorings, both the vertex and the edge version. Given a graph $G$, a mapping $f$ that assigns an integer from $\{1,\dots ,k\}$ to each vertex (resp.\ edge) of $G$ is an injective (edge) coloring of $G$ if $f(x)=f(y)$ implies that $x$ and $y$ are not in a common triangle nor at distance $2$ for any two vertices (resp.\ edges) $x$ and $y$ in $G$. The minimum number of colors $k$ for which there exists an injective (edge) coloring of $G$ is called the injective chromatic number (resp.\ injective chromatic index) of $G$ and is denoted by ${\chi }_i(G)$ (resp.\ ${\chi }_i^{\prime }(G)$). The vertex version of injective colorings in generalized Sierpiński graphs was studied in an earlier paper, where the authors determined the injective chromatic numbers of standard Sierpiński graphs, and asked about the values when $G$ is a cycle. We resolve this question by proving that ${\chi }_i(S_{C_k}^n)=3$ for every $n\ge 2$ and every $k\ge 3$. Moreover, we prove an almost conclusive result that ${\chi }_i(S_G^n)\in \{{\chi }_i(G),{\chi }_i(G)+1\}$ for any graph $G$ and any $n\ge 2$. For injective edge colorings we prove that ${\chi }_i^{\prime }(S_{K_3}^n)=5$ for all $n\ge 3$, while ${\chi }_i^{\prime }(S_{K_3}^2)=4$ and ${\chi }_i^{\prime }(S_{K_3}^1)=3$. Furthermore, if $G$ is a triangle-free graph, we prove that ${\chi }_i^{\prime }(S_G^n)\in \{{\chi }_i^{\prime }(S_G^3),{\chi }_i^{\prime }(S_G^3)+1\}$ for all $n\ge 4$, and provide some sufficient conditions on an injective edge coloring of the 3-dimensional Sierpiński graph over $G$, which ensure that ${\chi }_i^{\prime }(S_G^n)={\chi }_i^{\prime }(S_G^3)$.

17 pages, 10 figures