Extremal problems on detectable colorings of trees |
| |
Authors: | Henry Escuadro |
| |
Institution: | Department of Mathematics, Western Michigan University, Kalamazoo, MI 49008, USA |
| |
Abstract: | Let G be a connected graph of order 3 or more and let 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 is the k-tuple c(v)=(a1,a2,…,ak), where ai is the number of edges incident with v that are colored i (1?i?k). The coloring c is called detectable if distinct vertices have distinct color codes; while the detection number det(G) of G is the minimum positive integer k for which G has a detectable k-coloring. For each integer n?3, let DT(n) be the maximum detection number among all trees of order n and dT(n) the minimum detection number among all trees of order n. The numbers DT(n) and dT(n) are determined for all integers n?3. Furthermore, it is shown that for integers k?2 and n?3, there exists a tree T of order n having det(T)=k if and only if dT(n)?k?DT(n). |
| |
Keywords: | 05C05 05C15 05C70 |
本文献已被 ScienceDirect 等数据库收录! |
|