Mathematics – Combinatorics
Scientific paper
2011-11-21
Mathematics
Combinatorics
10 pages
Scientific paper
A coloring of the vertices of a graph G is said to be distinguishing} provided no nontrivial automorphism of G preserves all of the vertex colors. The distinguishing number of G, D(G), is the minimum number of colors in a distinguishing coloring of G. The distinguishing chromatic number of G, chi_D(G), is the minimum number of colors in a distinguishing coloring of G that is also a proper coloring. Recently the notion of a distinguishing coloring was extended to that of a list distinguishing coloring. Given an assignment L= {L(v) : v in V(G)} of lists of available colors to the vertices of G, we say that G is (properly) L-distinguishable if there is a (proper) distinguishing coloring f of G such that f(v) is in L(v) for all v. The list distinguishing number of G, D_l(G), is the minimum integer k such that G is L-distinguishable for any list assignment L with |L(v)| = k for all v. Similarly, the list distinguishing chromatic number of G, denoted chi_{D_l}(G) is the minimum integer k such that G is properly L-distinguishable for any list assignment L with |L(v)| = k for all v. In this paper, we study these distinguishing parameters for trees, and in particular extend an enumerative technique of Cheng to show that for any tree T, D_l(T) = D(T), chi_D(T)=chi_{D_l}(T), and chi_D(T) <= D(T) + 1.
Ferrara Michael
Gethner Ellen
Hartke Stephen G.
Stolee Derrick
Wenger Paul S.
No associations
LandOfFree
List Distinguishing Parameters of Trees does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with List Distinguishing Parameters of Trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and List Distinguishing Parameters of Trees will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-378284