Graphs with vertex-coloring and detectable 2-edge-weighting

Abstract

For a connected graph G of order |V(G)|≥3 and a k-edge-weighting c:E(G)→{1,2,…,k} of the edges of G, the code, codec(v), of a vertex v of G is the ordered k-tuple (ℓ1,ℓ2,…,ℓk), where ℓi is the number of edges incident with v that are weighted i. (i) The k-edge-weighting c is detectable if every two adjacent vertices of G have distinct codes. The minimum positive integer k for which G has a detectable k-edge-weighting is the detectable chromatic number det(G) of G. (ii) The k-edge-weighting c is a vertex-coloring if every two adjacent vertices u,v of G with codes 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 k for which G has a vertex-coloring k-edge-weighting is denoted by μ(G). In this paper, we have enlarged the known families of graphs with det(G)=μ(G)=2.

Keywords

• Detectable edge-weighting
• Vertex-coloring edge-weighting
• Cartesian product
• Tensor product