Article
Full entry |
PDF
(0.4 MB)
Feedback
PDF
(0.4 MB)
Feedback
Keywords:
detectable coloring; detection number; unicyclic graph
detectable coloring; detection number; unicyclic graph
Summary:
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)$.
References:
[1] M. Aigner, E. Triesch: Irregular assignments and two problems á la Ringel. Topics in Combinatorics and Graph Theory. (R. Bodendiek and R. Henn, eds.). Physica, Heidelberg (1990), 29–36. MR 1100017
[2] M. Aigner, E. Triesch, Z. Tuza: Irregular assignments and vertex-distinguishing edge-colorings of graphs. Combinatorics ’90, Proc. Conf., Gaeta/Italy 1990, Elsevier Science Pub., New York (1992), 1–9. MR 1195794
[3] A. C. Burris: On graphs with irregular coloring number $2$. Congr. Numerantium 100 (1994), 129–140. MR 1382313 | Zbl 0836.05029
[4] A. C. Burris: The irregular coloring number of a tree. Discrete Math. 141 (1995), 279–283. DOI 10.1016/0012-365X(93)E0225-S | MR 1336691 | Zbl 0829.05027
[5] G. Chartrand, H. Escuadro, F. Okamoto, P. Zhang: Detectable colorings of graphs. (to appear). MR 2212794
[6] G. Chartrand, P. Zhang: Introduction to Graph Theory. McGraw-Hill, Boston, 2005.
Search
Partner of
