Graphs with vertex-coloring and detectable 2-edge-weighting
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...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Taylor & Francis Group
2016-08-01
|
| Series: | AKCE International Journal of Graphs and Combinatorics |
| Subjects: | |
| Online Access: | http://www.sciencedirect.com/science/article/pii/S0972860016300913 |
| _version_ | 1828445537704083456 |
|---|---|
| author | N. Paramaguru R. Sampathkumar |
| author_facet | N. Paramaguru R. Sampathkumar |
| author_sort | N. Paramaguru |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-12-10T21:59:28Z |
| format | Article |
| id | doaj.art-988a8e3629a84bfbb2edf519092dca97 |
| institution | Directory Open Access Journal |
| issn | 0972-8600 |
| language | English |
| last_indexed | 2024-12-10T21:59:28Z |
| publishDate | 2016-08-01 |
| publisher | Taylor & Francis Group |
| record_format | Article |
| series | AKCE International Journal of Graphs and Combinatorics |
| spelling | doaj.art-988a8e3629a84bfbb2edf519092dca972022-12-22T01:31:57ZengTaylor & Francis GroupAKCE International Journal of Graphs and Combinatorics0972-86002016-08-0113214615610.1016/j.akcej.2016.06.008Graphs with vertex-coloring and detectable 2-edge-weightingN. Paramaguru0R. Sampathkumar1Mathematics Wing, Directorate of Distance Education, Annamalai University, Annamalainagar 608 002, IndiaMathematics Section, Faculty of Engineering and Technology, Annamalai University, Annamalainagar 608 002, IndiaFor 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.http://www.sciencedirect.com/science/article/pii/S0972860016300913Detectable edge-weightingVertex-coloring edge-weightingCartesian productTensor product |
| spellingShingle | N. Paramaguru R. Sampathkumar Graphs with vertex-coloring and detectable 2-edge-weighting AKCE International Journal of Graphs and Combinatorics Detectable edge-weighting Vertex-coloring edge-weighting Cartesian product Tensor product |
| title | Graphs with vertex-coloring and detectable 2-edge-weighting |
| title_full | Graphs with vertex-coloring and detectable 2-edge-weighting |
| title_fullStr | Graphs with vertex-coloring and detectable 2-edge-weighting |
| title_full_unstemmed | Graphs with vertex-coloring and detectable 2-edge-weighting |
| title_short | Graphs with vertex-coloring and detectable 2-edge-weighting |
| title_sort | graphs with vertex coloring and detectable 2 edge weighting |
| topic | Detectable edge-weighting Vertex-coloring edge-weighting Cartesian product Tensor product |
| url | http://www.sciencedirect.com/science/article/pii/S0972860016300913 |
| work_keys_str_mv | AT nparamaguru graphswithvertexcoloringanddetectable2edgeweighting AT rsampathkumar graphswithvertexcoloringanddetectable2edgeweighting |