Article ID Journal Published Year Pages File Type
4646489 AKCE International Journal of Graphs and Combinatorics 2016 11 Pages PDF
Abstract

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.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,