Upper bound for radio -chromatic number of graphs in connection with partition of vertex set
For a simple connected graph and a positive integer with , a radio -coloring of is a mapping such that holds for each pair of distinct vertices and of , where is the diameter of and is the distance between and in . The span of a radio -coloring is the number . The main aim of the radio -coloring pro...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Taylor & Francis Group
2020-01-01
|
| Series: | AKCE International Journal of Graphs and Combinatorics |
| Subjects: | |
| Online Access: | http://dx.doi.org/10.1016/j.akcej.2019.03.024 |
| _version_ | 1818441497459032064 |
|---|---|
| author | Laxman Saha |
| author_facet | Laxman Saha |
| author_sort | Laxman Saha |
| collection | DOAJ |
| description | For a simple connected graph and a positive integer with , a radio -coloring of is a mapping such that holds for each pair of distinct vertices and of , where is the diameter of and is the distance between and in . The span of a radio -coloring is the number . The main aim of the radio -coloring problem is to determine the minimum span of a radio -coloring of , denoted by . Due to NP-hardness of this problem, people are finding lower bounds for for particular families of graphs or general graphs . In this article, we concentrate on finding upper bounds of radio -chromatic number for general graphs and in consequence a coloring scheme depending on a partition of the vertex set . We apply these bounds to cycle graph and hypercube and show that it is sharp when is close to the diameter of these graphs. |
| first_indexed | 2024-12-14T18:29:11Z |
| format | Article |
| id | doaj.art-66e90f3245b44676a9f38495addd9d7a |
| institution | Directory Open Access Journal |
| issn | 0972-8600 2543-3474 |
| language | English |
| last_indexed | 2024-12-14T18:29:11Z |
| publishDate | 2020-01-01 |
| publisher | Taylor & Francis Group |
| record_format | Article |
| series | AKCE International Journal of Graphs and Combinatorics |
| spelling | doaj.art-66e90f3245b44676a9f38495addd9d7a2022-12-21T22:51:50ZengTaylor & Francis GroupAKCE International Journal of Graphs and Combinatorics0972-86002543-34742020-01-0117134235510.1016/j.akcej.2019.03.0241760552Upper bound for radio -chromatic number of graphs in connection with partition of vertex setLaxman Saha0Department of Mathematics, Balurghat CollegeFor a simple connected graph and a positive integer with , a radio -coloring of is a mapping such that holds for each pair of distinct vertices and of , where is the diameter of and is the distance between and in . The span of a radio -coloring is the number . The main aim of the radio -coloring problem is to determine the minimum span of a radio -coloring of , denoted by . Due to NP-hardness of this problem, people are finding lower bounds for for particular families of graphs or general graphs . In this article, we concentrate on finding upper bounds of radio -chromatic number for general graphs and in consequence a coloring scheme depending on a partition of the vertex set . We apply these bounds to cycle graph and hypercube and show that it is sharp when is close to the diameter of these graphs.http://dx.doi.org/10.1016/j.akcej.2019.03.024channel assignment problemradio -coloringradio -chromatic numberspan |
| spellingShingle | Laxman Saha Upper bound for radio -chromatic number of graphs in connection with partition of vertex set AKCE International Journal of Graphs and Combinatorics channel assignment problem radio -coloring radio -chromatic number span |
| title | Upper bound for radio -chromatic number of graphs in connection with partition of vertex set |
| title_full | Upper bound for radio -chromatic number of graphs in connection with partition of vertex set |
| title_fullStr | Upper bound for radio -chromatic number of graphs in connection with partition of vertex set |
| title_full_unstemmed | Upper bound for radio -chromatic number of graphs in connection with partition of vertex set |
| title_short | Upper bound for radio -chromatic number of graphs in connection with partition of vertex set |
| title_sort | upper bound for radio chromatic number of graphs in connection with partition of vertex set |
| topic | channel assignment problem radio -coloring radio -chromatic number span |
| url | http://dx.doi.org/10.1016/j.akcej.2019.03.024 |
| work_keys_str_mv | AT laxmansaha upperboundforradiochromaticnumberofgraphsinconnectionwithpartitionofvertexset |