Back to Search
Start Over
The k-Distance Independence Number and 2-Distance Chromatic Number of Cartesian Products of Cycles.
- Source :
-
Bulletin of the Malaysian Mathematical Sciences Society . Jul2018, Vol. 41 Issue 3, p1377-1391. 15p. - Publication Year :
- 2018
-
Abstract
- A set S⊆V(G)<inline-graphic></inline-graphic> is a k-distance independent set of a graph G if the distance between every two vertices of S is greater than k. The k-distance independence number αk(G)<inline-graphic></inline-graphic> of G is the maximum cardinality over all k-distance independent sets in G. A k-distance coloring of G is a function f from V(G) onto a set of positive integers (colors) such that for any two distinct vertices u and v at distance less than or equal to k we have f(u)≠f(v)<inline-graphic></inline-graphic>. The k-distance chromatic number of a graph G is the smallest number of colors needed to have a k-distance coloring of G. The k-distance independence numbers and 2-distance chromatic numbers of Cartesian products of cycles are considered. A computer-aided method with the isomorphic rejection is used to determine the k-distance independence numbers of Cartesian products of cycles. By using these results, several lower and upper bounds on the maximal cardinality AqL(n,d)<inline-graphic></inline-graphic> of a q-ary Lee code of length n with a minimum distance at least d are improved. It is also established that the 2-distance chromatic number of G equals |V(G)|α(G2)<inline-graphic></inline-graphic> for G=Cm□Cn□Ck<inline-graphic></inline-graphic>, whenever k≥3<inline-graphic></inline-graphic> and (m,n)∈{(3,3),(3,4),(3,5),(4,4)}<inline-graphic></inline-graphic> or k, m and n are all multiples of seven. Moreover, it is shown that the 2-distance chromatic number of the three-dimensional square lattice is equal to seven. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 01266705
- Volume :
- 41
- Issue :
- 3
- Database :
- Academic Search Index
- Journal :
- Bulletin of the Malaysian Mathematical Sciences Society
- Publication Type :
- Academic Journal
- Accession number :
- 130360251
- Full Text :
- https://doi.org/10.1007/s40840-016-0397-0