A new graph parameter and a construction of larger graph without increasing radio k-chromatic number

作者：Sarkar Ushnish; Adhikari Avishek^*

来源：Journal of Combinatorial Optimization, 2017, 33(4): 1365-1377.

DOI：10.1007/s10878-016-0041-9

• Radio k-coloring
• Hole
• Maximum degree
• Domination number
• Path covering number

For a positive integer , the radio k-coloring problem is an assignment L of non-negative integers (colors) to the vertices of a finite simple graph G satisfying the condition , for any two distinct vertices u, v of G and d(u, v) being distance between u, v. The span of L is the largest integer assigned by L, while 0 is taken as the smallest color. An -coloring on G is a radio k-coloring on G of minimum span which is referred as the radio k-chromatic number of G and denoted by . An integer h, , is a hole in a -coloring on G if h is not assigned by it. In this paper, we construct a larger graph from a graph of a certain class by using a combinatorial property associated with consecutive holes in any -coloring of a graph. Exploiting the same property, we introduce a new graph parameter, referred as -hole index of G and denoted by .

• 出版日期2017-5