Graphs associated with matrices over finite fields and their endomorphisms in memory of Professor Michael Neumann and Professor Uri Rothblum

Li Ping Huang, Zejun Huang, Chi Kwong Li, Nung Sing Sze

Research output: Journal article publicationJournal articleAcademic researchpeer-review

17 Citations (Scopus)

Abstract

Let Fm×nbe the set of m×n matrices over a field F. Consider a graph G=(Fm×n,∼) with Fm×nas the vertex set such that two vertices A,B∈Fm×nare adjacent if rank(A-B)=1. We study graph properties of G when F is a finite field. In particular, G is a regular connected graph with diameter equal to min{m,n}; it is always Hamiltonian. Furthermore, we determine the independence number, chromatic number and clique number of G. These results are used to characterize the graph endomorphisms of G, which extends Hua's fundamental theorem of geometry on Fm×n.
Original languageEnglish
Pages (from-to)2-25
Number of pages24
JournalLinear Algebra and Its Applications
Volume447
DOIs
Publication statusPublished - 15 Apr 2014

Keywords

  • Chromatic number
  • Endomorphism
  • Finite field
  • Graph
  • Independence number
  • Matrix

ASJC Scopus subject areas

  • Algebra and Number Theory
  • Numerical Analysis
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics

Cite this