2015/12/22 by Zhe Han, Mei Lu, Han, Zhe +1
Computer Science · Engineering · Mathematics · #05C15 #68R10 #94B05 #94B65 #Coding theory and cryptography #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #graph theory and CDMA systems #math.CO #msc:05C15 #msc:68R10 #msc:94B05 #msc:94B65
paper · pdf · doi:10.48550/arxiv.1512.07239
9 pages
arxiv created 2015/12/22 · openalex publication_date 2015/12/22 · arxiv updated 2015/12/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper, we propose a new family of graphs, matrix graphs, whose vertex set \mathbbFN× nq is the set of all N× n matrices over a finite field \mathbbFq for any positive integers N and n. And any two matrices share an edge if the rank of their difference is 1. Next, we give some basic properties of such graphs and also consider two coloring problems on them. Let χ'd(N× n, q) (resp. χd(N× n, q)) denote the minimum number of colors necessary to color the above matrix graph so that no two vertices that are at a distance at most d (resp. exactly d) get the same color. These two problems were proposed in the study of scalability of optical networks. In this paper, we determine the exact value of χ'd(N× n,q) and give some upper and lower bounds on χd(N× n,q).