Published January 1, 2011
| Version v1
Publication
Open
Improved Bounds for Radio<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>k</mml:mi></mml:math>-Chromatic Number of Hypercube<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msub><mml:mi>Q</mml:mi><mml:mi>n</mml:mi></mml:msub></mml:mrow></mml:math>
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). Radiok-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 radiok-chromatic number of hypercubeQn, 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 ofQnwhenn≡2(mod 4).
Translated Descriptions
⚠️
This is an automatic machine translation with an accuracy of 90-95%
Translated Description (Arabic)
هناك عدد من مشكلات تلوين الرسم البياني لها جذورها في مشكلة اتصال تعرف باسم مشكلة تخصيص القناة. مشكلة تخصيص القناة هي مشكلة تعيين القنوات (الأعداد الصحيحة غير السالبة) للمحطات بطريقة مثالية بحيث يتم تجنب التداخل كما ذكر هيل (2005). راديوk- تلوين الرسم البياني هو نوع خاص من مشكلة تخصيص القناة. أعطى Kchikech et al. (2005) حدًا أدنى وأعلى للعدد اللوني للراديوk من المكعب الفائقQn، وتم الحصول على تحسين لحدهم الأدنى من قبل Kola و Panigrahi (2010). في هذه الورقة، قمنا بتحسين الحد الأدنى لكولا وآخرون وكذلك الحد الأعلى لكشيكيك وآخرون. أيضًا، تتفق حدودنا على ما يقرب من العدد المتقابل من Qn عندماn 2(mod 4).Translated Description (French)
Un certain nombre de problèmes de coloration de graphes ont leurs racines dans un problème de communication connu sous le nom de problème d'attribution de canal. Le problème d'attribution de canaux est le problème d'attribution de canaux (entiers non négatifs) aux stations de manière optimale afin d'éviter les interférences comme indiqué par Hale (2005). La coloration kradio d'un graphique est un type particulier de problème d'attribution de canal. Kchikech et al. (2005) ont donné une limite inférieure et une limite supérieure pour le nombre radiok -chromatique de l'hypercubeQn, et une amélioration de leur limite inférieure a été obtenue par Kola et Panigrahi (2010). Dans cet article, nous améliorons davantage la limite inférieure de Kola et al. ainsi que la limite supérieure de Kchikeck et al. De plus, nos limites s'accordent pour un nombre presque antipodal deQnlorsquen≡2(mod 4).Translated Description (Spanish)
Una serie de problemas de coloración de gráficos tienen sus raíces en un problema de comunicación conocido como el problema de asignación de canales. El problema de asignación de canales es el problema de asignar canales (enteros no negativos) a las estaciones de una manera óptima, de modo que se evite la interferencia, según lo informado por Hale (2005). La radiok-coloración de un gráfico es un tipo especial de problema de asignación de canales. Kchikech et al. (2005) han dado un límite inferior y un límite superior para el número radio k-cromático del hipercuboQn, y Kola y Panigrahi (2010) obtuvieron una mejora de su límite inferior. En este documento, mejoramos aún más el límite inferior de Kola et al., así como el límite superior de Kchikeck et al. Además, nuestros límites coinciden para un número casi antipodal deQncuandon≡2(mod 4).Files
961649.pdf.pdf
Files
(15.9 kB)
| Name | Size | Download all |
|---|---|---|
|
md5:677d0755dcf33a4eee29eedfe2f3fbfe
|
15.9 kB | Preview Download |
Additional details
Additional titles
- Translated title (Arabic)
- حدود محسنة للراديو<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>k</mml:mi></mml:math>- العدد اللوني للمكعب الفائق<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msub><mml:mi></mml:mi><mml:mi> Qn</mml:mi></mml:msub></mml:mrow></mml:math>
- Translated title (French)
- Limites améliorées pour Radio<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>k</mml:mi></mml:math>-Chromatic Number of Hypercube<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msub><mml:mi>Q</mml:mi><mml:mi>n</mml:mi></mml:msub></mml:mrow></mml:math>
- Translated title (Spanish)
- Límites mejorados para Radio<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>k</mml:mi></mml:math> - Número cromático de hipercubo<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msub><mml:mi>Q</mml:mi><mml:mi>n</mml:mi></mml:msub></mml:mrow></mml:math>
Identifiers
- Other
- https://openalex.org/W2042843122
- DOI
- 10.1155/2011/961649
References
- https://openalex.org/W1557510447
- https://openalex.org/W1995401759
- https://openalex.org/W2002366650
- https://openalex.org/W2028436572
- https://openalex.org/W2056891496
- https://openalex.org/W2726943575