Improved Bounds for Radio k-Chromatic Number of Hypercube Qn
A number of graph coloring problems have their roots in a communication problem known as the channel assignment problem. The channel assignment problem is the problem of assigning channels (nonnegative integers) to the stations in an optimal way such that interference is avoided as reported by Hale...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2011-01-01
|
| Series: | International Journal of Mathematics and Mathematical Sciences |
| Online Access: | http://dx.doi.org/10.1155/2011/961649 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849691944858419200 |
|---|---|
| author | Laxman Saha Pratima Panigrahi Pawan Kumar |
| author_facet | Laxman Saha Pratima Panigrahi Pawan Kumar |
| author_sort | Laxman Saha |
| collection | DOAJ |
| description | A number of graph coloring problems have their roots in a communication problem known as the channel assignment problem. The channel assignment problem is the problem of assigning channels (nonnegative integers) to the stations in an optimal way such that interference is avoided as reported by Hale (2005). Radio k-coloring of a graph is a special type of channel assignment problem. Kchikech et al. (2005) have given a lower and an upper bound for radio k-chromatic number of hypercube Qn, and an improvement of their lower bound was obtained by Kola and Panigrahi (2010). In this paper, we further improve Kola et al.'s lower bound as well as Kchikeck et al.'s upper bound. Also, our bounds agree for nearly antipodal number of Qn when n≡2 (mod 4). |
| format | Article |
| id | doaj-art-b3e034fa12e44961ab3fe80148d4149b |
| institution | DOAJ |
| issn | 0161-1712 1687-0425 |
| language | English |
| publishDate | 2011-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | International Journal of Mathematics and Mathematical Sciences |
| spelling | doaj-art-b3e034fa12e44961ab3fe80148d4149b2025-08-20T03:20:51ZengWileyInternational Journal of Mathematics and Mathematical Sciences0161-17121687-04252011-01-01201110.1155/2011/961649961649Improved Bounds for Radio k-Chromatic Number of Hypercube QnLaxman Saha0Pratima Panigrahi1Pawan Kumar2Department of Mathematics, IIT Kharagpur, Kharagpur 721302, IndiaDepartment of Mathematics, IIT Kharagpur, Kharagpur 721302, IndiaDepartment of Mathematics, IIT Kharagpur, Kharagpur 721302, IndiaA number of graph coloring problems have their roots in a communication problem known as the channel assignment problem. The channel assignment problem is the problem of assigning channels (nonnegative integers) to the stations in an optimal way such that interference is avoided as reported by Hale (2005). Radio k-coloring of a graph is a special type of channel assignment problem. Kchikech et al. (2005) have given a lower and an upper bound for radio k-chromatic number of hypercube Qn, and an improvement of their lower bound was obtained by Kola and Panigrahi (2010). In this paper, we further improve Kola et al.'s lower bound as well as Kchikeck et al.'s upper bound. Also, our bounds agree for nearly antipodal number of Qn when n≡2 (mod 4).http://dx.doi.org/10.1155/2011/961649 |
| spellingShingle | Laxman Saha Pratima Panigrahi Pawan Kumar Improved Bounds for Radio k-Chromatic Number of Hypercube Qn International Journal of Mathematics and Mathematical Sciences |
| title | Improved Bounds for Radio k-Chromatic Number of Hypercube Qn |
| title_full | Improved Bounds for Radio k-Chromatic Number of Hypercube Qn |
| title_fullStr | Improved Bounds for Radio k-Chromatic Number of Hypercube Qn |
| title_full_unstemmed | Improved Bounds for Radio k-Chromatic Number of Hypercube Qn |
| title_short | Improved Bounds for Radio k-Chromatic Number of Hypercube Qn |
| title_sort | improved bounds for radio k chromatic number of hypercube qn |
| url | http://dx.doi.org/10.1155/2011/961649 |
| work_keys_str_mv | AT laxmansaha improvedboundsforradiokchromaticnumberofhypercubeqn AT pratimapanigrahi improvedboundsforradiokchromaticnumberofhypercubeqn AT pawankumar improvedboundsforradiokchromaticnumberofhypercubeqn |