On detectable colorings of graphs

Escuadro, Henry ; Zhang, Ping

Mathematica Bohemica, Tome 130 (2005) no. 4, pp. 427-445.

Résumé

Let $G$ be a connected graph of order $n \ge 3$ and let $c\: E(G) \rightarrow \lbrace 1, 2, \ldots , k\rbrace $ be a coloring of the edges of $G$ (where adjacent edges may be colored the same). For each vertex $v$ of $G$, the color code of $v$ with respect to $c$ is the $k$-tuple $c(v) = (a_1, a_2, \cdots , a_k)$, where $a_i$ is the number of edges incident with $v$ that are colored $i$ ($1 \le i \le k$). The coloring $c$ is detectable if distinct vertices have distinct color codes. The detection number $\det (G)$ of $G$ is the minimum positive integer $k$ for which $G$ has a detectable $k$-coloring. We establish a formula for the detection number of a path in terms of its order. For each integer $n \ge 3$, let $D_u(n)$ be the maximum detection number among all unicyclic graphs of order $n$ and $d_u(n)$ the minimum detection number among all unicyclic graphs of order $n$. The numbers $D_u(n)$ and $d_u(n)$ are determined for all integers $n \ge 3$. Furthermore, it is shown that for integers $k \ge 2$ and $n \ge 3$, there exists a unicyclic graph $G$ of order $n$ having $\det (G)=k$ if and only if $d_u(n) \le k \le D_u(n)$.

Détail

DOI : 10.21136/MB.2005.134214

Classification : 05C15, 05C70
Keywords: detectable coloring; detection number; unicyclic graph