Study On Commutative Graphs And Unit Graphs Of Boolean Matrices

A matrix consisting of only 0 and 1 elements is called a Boolean matrix.Boolean matrix is widely used in logic,communication engineering,combination theory,graph theory,semigroup theory,fuzzy set theory,computer science and many other fields.The main contents of this paper are:Commuting graphs of cells of Boolean matrices,the complement graphs of commuting graphs of cells of Boolean matrices,and the unit graphs of Boolean matrices.The details are as follows:In the first chapter,we introduce the research background of Boolean matrices,commutative graphs and unit graphs.In chapter 2,we give the basic knowledge,definition and symbols involved in this paper.In chapter 3,we mainly study the commuting graphs of cells of Boolean matrices.Let Mn(B)denote the set of all n × n boolean matrices.A n × n Boolean matrix with only one non-zero term 1 is called a cell.If the nonzero entry occurs in the ith row and the jth column,then we denote this cell by Ei,j.The commutativity of cells has a crucial influence on the commutativity of matrix multiplication.For this reason,we study the commuting graph Γ(Cn)of cells,where Cn (?)[Mn(B)is the set of all n× n cells.For any two different vertices Ei,j and Es,t in Γ(Cn),Ei,j and Es,t are adjacent if and only if Ei,jEs,t=Es,tEi,j.We obtain the basic structure of commuting graphs of cells,including diameters,girths,independent numbers,domination numbers,Hamiltonian cycles,chromatic numbers,Wiener indices,clique numbers and automorphisms of commuting graphs.In chapter 4,we investigate the complement graphs Γ’(Cn)of commuting graphs of cells of Boolean matrices.All the n × n cell sets are regarded as the vertex set of Γ’(Cn).For any two different vertices Ei,j and Es,t in Γ’(Cn).Ei,j and Es,t are adjacent if and only if Ei,j and Es,t are not adjacent in Γ(Cn).We determine the diameters of Γ’(Cn),degree of vertices,domination numbers,chromatic numbers,clique numbers,Hamiltonian cycles,and automorphisms of the complement.We study in chapter 5 the unit graphs G(Mn(B))of Boolean matrices.For Boolean matrices A and B in G(Mn(B)),A and B are adjacent if and only if A+B is a unit.We get the number of vertices in the unit graphs,the distance between different types of matrices,the degrees,clique numbers,and planarity of vertices.