Antypodalna radiowa liczba chromatyczna grafu

• Autorzy: Kosowski A. , Kubale M.

Warianty tytułu

EN

Antipodal radio chromatic number of graphs

• Języki publikacji: PL

Abstrakty

PL

Antypodalne kolorowanie grafu jest modelem kolorowania radiowego grafów spójnych, w którym dla każdej pary wierzchołków suma odległości kolorów i odległości wierzchołków w grafie musi być nie mniejsza od średnicy grafu. Zagadnienie optymalizacyjne polega na minimalizacji największej użytej wartości koloru (tzw. antypodalnej radiowej liczby chromatycznej grafu). Problem radiowego kolorowania antypodalnego znajduje zastosowanie w dziedzinie przydziału częstotliwości roboczych stacjom radiowym oraz w sieciach telefonii komórkowej. Opisane zostały podstawowe zasady i właściwości antypodalnego kolorowania grafów. Zebrano publikowane w literaturze przedmiotu twierdzenia i uzupełniono wnioskami wynikającymi z własnych badań. Podano oszacowania antypodalnej liczby chromatycznej grafu w przypadku ogólnym oraz dokładne wartości antypodalnej liczby chromatycznej dla grafów pełnych k-dzielnych, kół i dwugwiazd. Pokazano zarówno górne, jak i dolne oszacowanie antypodalnej liczby chromatycznej przy pomocy średnicowej radiowej liczby chromatycznej. Wyprowadzono oszacowania górne i dolne na antypodalną liczbę chromatyczną ścieżek i cykli oraz wysunięto (popartą wynikami badań) hipotezę, ze wskazane oszacowanie górne jest dokładne.

EN

The paper deals with the subject of antipodal graph coloring. Antipodal graph coloring is a model of k-radiocoloring of graphs. In contrast to the classical method, the difference in colors assigned to vertices u, v is inversely proportional to the distance between u and v. The sum of the difference of colors and distance of vertices may for no pair of vertices be less than the diameter of the graph. The aim is to find such a radiocoloring of G, that the maximal color used is as small as possible. The model of antipodal coloring may be applied in practice in the field of frequency assignment for radio stations and in cellular networks. In the paper we study basic principles and properties of the graph antipodal radiocoloring problem. Since the general problem is NP-hard, we give lower and upper bounds for the radiochromatic number. Exact values of the radio chromatic number are given for complete multipartite graphs, wheels and double stars. Upper and lower bounds of the antipodal radio chromatic number are shown for paths and cycles.

• Wydawca: Wydział Elektroniki, Telekomunikacji i Informatyki Politechniki Gdańskiej
• Czasopismo: Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne
• Rocznik: 2003
• Tom: nr 2
• Strony: 487--494
• Opis fizyczny: Bibliogr. 8 poz., 3 rys.

Twórcy

autor

Kosowski A.

• Katedra Podstaw Informatyki, Politechnika Gdańska

autor

Kubale M.

• Katedra Podstaw Informatyki, Politechnika Gdańska

Bibliografia

• [1] Chartrand G., Erwin D., Zhang P.: Radio antipodal colorings of cycles. Congressus Numerantium, Vol. 144, pp. 129-141, 2000.
• [2] Chartrand G., Erwin D., Zhang P.: A graph labeling problem suggested by FM channel restriction. University of Massachusetts, 2001.
• [3] Chartrand G., Erwin D., Zhang P.: Radio antipodal colorings of graphs. Mathematica Bohemica, Vol. 127, pp. 57-69, 2002.
• [4] Fotakis D., Pantziau G., Pentaris G., Spirakis P.: Frequency assignment in mobile and radio networks. DIMACS series in Discrete Mathematics, 2001.
• [5] Janczewski R.: Radiowe liczby k-chromatyczne. Politechnika Gdańska, Wydział ETI, na prawach rękopisu, 2001.
• [6] Kubale M.: Introduction to Computational Complexity and Algorithmic Graph Coloring. Wyd. GTN, Gdansk 1998.
• [7] Kubale M., Kosowski A.: Algorytmy radiowego kolorowania grafów. Zesz.Nauk.P.Śląsk., 2002 nr 1556, Automatyka zastosowań 136.
• [8] Kubale M. et al: Optymalizacja dyskretna. Modele i metody kolorowania grafów. Wyd. WNT, Warszawa 2002.