首页 | 本学科首页   官方微博 | 高级检索  
     检索      


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 View the MathML source 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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号