| Title:
|
On detectable colorings of graphs (English) |
| Author:
|
Escuadro, Henry |
| Author:
|
Zhang, Ping |
| Language:
|
English |
| Journal:
|
Mathematica Bohemica |
| ISSN:
|
0862-7959 (print) |
| ISSN:
|
2464-7136 (online) |
| Volume:
|
130 |
| Issue:
|
4 |
| Year:
|
2005 |
| Pages:
|
427-445 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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)$. (English) |
| Keyword:
|
detectable coloring |
| Keyword:
|
detection number |
| Keyword:
|
unicyclic graph |
| MSC:
|
05C15 |
| MSC:
|
05C70 |
| idZBL:
|
Zbl 1111.05034 |
| idMR:
|
MR2182387 |
| DOI:
|
10.21136/MB.2005.134214 |
| . |
| Date available:
|
2009-09-24T22:23:06Z |
| Last updated:
|
2020-07-29 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/134214 |
| . |
| Reference:
|
[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 |
| Reference:
|
[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 |
| Reference:
|
[3] A. C. Burris: On graphs with irregular coloring number $2$.Congr. Numerantium 100 (1994), 129–140. Zbl 0836.05029, MR 1382313 |
| Reference:
|
[4] A. C. Burris: The irregular coloring number of a tree.Discrete Math. 141 (1995), 279–283. Zbl 0829.05027, MR 1336691, 10.1016/0012-365X(93)E0225-S |
| Reference:
|
[5] G. Chartrand, H. Escuadro, F. Okamoto, P. Zhang: Detectable colorings of graphs.(to appear). MR 2212794 |
| Reference:
|
[6] G. Chartrand, P. Zhang: Introduction to Graph Theory.McGraw-Hill, Boston, 2005. |
| . |
