Please use this identifier to cite or link to this item: https://idr.l3.nitk.ac.in/jspui/handle/123456789/17069
Full metadata record
DC FieldValueLanguage
dc.contributor.advisorKola, Srinivasa Rao.-
dc.contributor.authorK, Niranjan P.-
dc.date.accessioned2022-02-01T10:34:32Z-
dc.date.available2022-02-01T10:34:32Z-
dc.date.issued2021-
dc.identifier.urihttp://idr.nitk.ac.in/jspui/handle/123456789/17069-
dc.description.abstractThe frequency assignment problem is the problem of assigning frequencies to transmitters in an optimal way and with no interference. Interference can occur if transmitters located sufficiently close to each other receive close frequencies. The frequency assignment problem motivates many graph coloring problems. Motivated by this, we study radio k-coloring and k-distance coloring of graphs. In this thesis, we study radio k-coloring of paths, trees, Cartesian product of graphs and corona of graphs; k-distance coloring of trees, cycles and cactus graphs. A radio k-coloring of a simple connected graph G is an assignment f of positive integers (colors) to the vertices of G such that for every pair of distinct vertices u and v in G, j f (u)􀀀 f (v)j is at least 1+k􀀀d(u;v). The span of f , rck( f ), is the maximum color assigned by f . The radio k-chromatic number rck(G) is minfrck( f ) : f is a radio k-coloring of Gg. If d is the diameter of G, then a radio d-coloring and the radio d-chromatic number are referred as a radio coloring and the radio number rn(G) of G. Since finding the radio k-chromatic number is highly nontrivial, it is known for very few graphs and that too for some particular values of k only. For k 6, we determine the radio k-chromatic number of path Pn for 2n+1 7 k n􀀀4 if k is odd and for 2n􀀀4 5 k n􀀀5 if k is even. For some classes of trees, we obtain an upper bound for the radio k-chromatic number when k is at least the diameter of the tree. Also, for the same, we give a lower bound which matches with the upper bound when k and the diameter of the tree are of the same parity. Further, we determine the radio d-chromatic number of larger trees constructed from the trees of diameter d in some subclasses of the above classes. We determine the radio number for some classes of the Cartesian product of complete graphs and cycles. We obtain a best possible upper bound for the radio k-chromatic number of corona G H of arbitrary graphs G and H. Also, we obtain a lower bound and an improved upper bound for the radio number of Qn H and P2p+1 H. A k-distance coloring of a simple connected graph G is an assignment f of positive integers to the vertices of G such that no two vertices at distance less than or equal to k receive the same color. If a is the maximum color assigned by f , then f is referred as a k-distance a-coloring. The k-distance chromatic number ck(G) is the minimum a such that G has a k-distance a-coloring. We determine the k-distance chromatic number for trees and cycles. Also, we determine the 2-distance chromatic number of cactus graphs.en_US
dc.language.isoenen_US
dc.publisherNational Institute of Technology Karnataka, Surathkalen_US
dc.subjectDepartment of Mathematical and Computational Sciencesen_US
dc.subjectradio k-coloringen_US
dc.subjectSpanen_US
dc.subjectradio k-chromatic numberen_US
dc.subjectradio coloringen_US
dc.subjectradio numberen_US
dc.subjectk-distance coloringen_US
dc.subjectdistance coloringen_US
dc.subjectk-distance chromatic numberen_US
dc.subject2-distance coloringen_US
dc.subject2-distance chromatic numberen_US
dc.titleRadio k-Coloring and k-Distance Coloring of Graphsen_US
dc.typeThesisen_US
Appears in Collections:1. Ph.D Theses

Files in This Item:
File Description SizeFormat 
165069 MA16F03 - Niranjan P K.pdf804.46 kBAdobe PDFThumbnail
View/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.