Abstract | ||
---|---|---|
For edges e and f in a connected graph G, the distance d(e, f) between e and f is the minimum nonnegative integer f for which there exists a sequence e = e(0), e(1),..., e(l) = f of edges of G such that e(i) and e(i+1) are adjacent for i = 0, 1,..., l - 1. Let c be a proper edge coloring of G using k distinct colors and let D = {C-1, C-2,..., C-k} be an ordered partition of E (G) into the resulting edge color classes of c. For an edge e of G, the color code c(D) (e) of e is the k-tuple (d(e, C-1), d(e, C-2),..., d(e, C-k)), where d(e, C-i) = min{d(e, f) : f is an element of C-i} for 1 <= i <= k. If distinct edges have distinct color codes, then c is called a resolving edge coloring of G. The resolving edge chromatic number X,e(G) is the minimum number of colors in a resolving edge coloring of G. Bounds for the resolving edge chromatic number of a connected graph are established in terms of its size and diameter and in terms of its size and girth. All nontrivial connected graphs of size m with resolving edge chromatic number 3 or m are characterized. It is shown that for each pair k, m of integers with 3 <= k <= m, there exists a connected graph G of size m with chi(re)(G) = k. Resolving edge chromatic numbers of complete graphs are studied. |
Year | Venue | Keywords |
---|---|---|
2005 | ARS COMBINATORIA | distance, resolving decomposition, resolving edge coloring |
Field | DocType | Volume |
Discrete mathematics,Graph,Complete coloring,Combinatorics,Mathematics | Journal | 74 |
ISSN | Citations | PageRank |
0381-7032 | 4 | 1.31 |
References | Authors | |
3 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Gary Chartrand | 1 | 4 | 1.31 |
Varaporn Saenpholphat | 2 | 30 | 5.60 |
Ping Zhang | 3 | 292 | 47.70 |