An upper bound of radio k -coloring problem and its integer linear programming model
- PDF / 614,648 Bytes
- 10 Pages / 595.276 x 790.866 pts Page_size
- 13 Downloads / 163 Views
(0123456789().,-volV)(0123456789(). ,- volV)
An upper bound of radio k-coloring problem and its integer linear programming model Elsayed M. Badr1 • Mahmoud I. Moussa2
Springer Science+Business Media, LLC, part of Springer Nature 2019
Abstract For a positive integer k, a radio k-coloring of a simple connected graph G = (V(G), E(G)) is a mapping f : VðGÞ ! f0; 1; 2; . . .g such that jf ðuÞ f ðvÞj k þ 1 dðu; vÞ for each pair of distinct vertices u and v of G, where d(u, v) is the distance between u and v in G. The span of a radio k-coloring f, rck(f), is the maximum integer assigned by it to some vertex of G. The radio k-chromatic number, rck(G) of G is min{rck(f)}, where the minimum is taken over all radio k-colorings f of G. If k is the diameter of G, then rck(G) is known as the radio number of G. In this paper, we propose an improved upper bound of radio k-chromatic number for a given graph against the other which is due to Saha and Panigrahi (in: Arumugan, Smyth (eds) Combinatorial algorithms (IWOCA 2012). Lecure notes in computer science, vol 7643, Springer, Berlin, 2012). The computational study shows that the proposed algorithm overcomes the previous algorithm. We introduce a polynomial algorithm [differs from the other that is due to Liu and Zhu (SIAM J Discrete Math 19(3):610–621, 2005)] which determines the radio number of the path graph Pn. Finally, we propose a new integer linear programming model for the radio k-coloring problem. The computational study between the proposed algorithm and LINGO solver shows that the proposed algorithm overcomes LINGO solver. Keywords Radio k-coloring Radio number Upper bound Path Cycles Binomial tree Triangular snakes Ladder Friendship and book graphs Mathematics Subject Classification 05CO7 05C12 05C15
1 Introduction Motivated by the channel assignment problem proposed by Hale [3] in wireless networks, radio labeling in graphs has been studied from various perspectives. Let G = (V, E) be a graph, simple, connected and undirected. Let diam (G) = d and k B d be a positive integer. We use standard terms or notations as used in common texts such as [4, 5]. For a positive integer k, a radio k-coloring f of a simple connected graph G is an assignment of non-negative integers & Elsayed M. Badr [email protected] Mahmoud I. Moussa [email protected] 1
Scientific Computing Department, Faculty of Computers and Informatics, Benha University, Benha, Egypt
2
Computer Science Department, Faculty of Computers and Informatics, Benha University, Benha, Egypt
to the vertices of G such that for every two distinct vertices u and v of G, jf ðuÞ f ðvÞ j k þ 1 dðu; vÞ. The span of a radio k-coloring f, rck(f), is the maximum integer assigned by f to some vertex of G. The radio k-chromatic number, rck(G) of G is min{rck (f)}, where the minimum is taken over all radio k-colorings f of G. If k is the diameter of G, then rck(G) is known as the radio number and is denoted by rn(G). Radio number of Pn and Cn [2], trees [6], power of cycles [7], gener
Data Loading...
