Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4646489 | AKCE International Journal of Graphs and Combinatorics | 2016 | 11 Pages |
For a connected graph GG of order |V(G)|≥3|V(G)|≥3 and a kk-edge-weighting c:E(G)→{1,2,…,k} of the edges of GG, the code , codec(v)codec(v), of a vertex vv of GG is the ordered kk-tuple (ℓ1,ℓ2,…,ℓk)(ℓ1,ℓ2,…,ℓk), where ℓiℓi is the number of edges incident with vv that are weighted ii. (i) The kk-edge-weighting cc is detectable if every two adjacent vertices of GG have distinct codes. The minimum positive integer kk for which GG has a detectable kk-edge-weighting is the detectable chromatic number det(G)det(G) of GG. (ii) The kk-edge-weighting cc is a vertex-coloring if every two adjacent vertices u,vu,v of GG with codes codec(u)=(ℓ1,ℓ2,…,ℓk)codec(u)=(ℓ1,ℓ2,…,ℓk) and codec(v)=(ℓ1′,ℓ2′,…,ℓk′) have 1ℓ1+2ℓ2+⋯+kℓk≠1ℓ1′+2ℓ2′+⋯+kℓk′. The minimum positive integer kk for which GG has a vertex-coloring kk-edge-weighting is denoted by μ(G)μ(G). In this paper, we have enlarged the known families of graphs with det(G)=μ(G)=2det(G)=μ(G)=2.