Henry Escuadro, Ping Zhang, Department of Mathematics, Western Michigan University, Kalamazoo, MI 49008, USA, e-mail: ping.zhang@wmich.edu
Abstract: Let $G$ be a connected graph of order $n \ge3$ and let $c E(G) \rightarrow\{1, 2, \ldots, k\}$ 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 \ge3$, 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 \ge3$. Furthermore, it is shown that for integers $k \ge2$ and $n \ge3$, 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)$.
Keywords: detectable coloring, detection number
Classification (MSC 2000): 05C15, 05C70
Full text available as PDF (smallest), as compressed PostScript (.ps.gz) or as raw PostScript (.ps).
Access to the full text of journal articles on this site is restricted to the subscribers of Myris Trade. To activate your access, please contact Myris Trade at myris@myris.cz.
