The minimum rank of universal adjacency matrices

DOI10.1016/J.LAA.2012.05.033MaRDI QIDQ448355zbMATH OpenOpenAlexWikidataFDO

Authors Yizheng Fan, Shaun M. Fallat, B. Ahmadi, F. Alinaghipour, K. Meagher, S. Nasserasr

Publication date 6 September 2012

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1112.1718

zbMATH Keywords

graphLaplacian matrixadjacency matrixcyclepathminimum universal rankuniversal adjacency matrix

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Eigenvalues, singular values, and eigenvectors (15A18) Paths and cycles (05C38) Vector spaces, linear dependence, rank, lineability (15A03) Commutativity of matrices (15A27)

Abstract: In this paper we introduce a new parameter for a graph called the {it minimum universal rank}. This parameter is similar to the minimum rank of a graph. For a graph $G$ the minimum universal rank of $G$ is the minimum rank over all matrices of the form [ U(alpha, �eta, gamma, delta) = alpha A + �eta I + gamma J + delta D ] where $A$ is the adjacency matrix of $G$, $J$ is the all ones matrix and $D$ is the matrix with the degrees of the vertices in the main diagonal, and $$ are scalars. Bounds for general graphs based on known graph parameters are given, as is a formula for the minimum universal rank for regular graphs based on the multiplicity of the eigenvalues of $A$. The exact value of the minimum universal rank of some families of graphs are determined, including complete graphs, complete bipartite graph, paths and cycles. Bounds on the minimum universal rank of a graph obtained by deleting a single vertex are established. It is shown that the minimum universal rank is not monotone on induced subgraphs, but bounds based on certain induced subgraphs, including bounds on the union of two graphs, are given. Finally we characterize all graphs with minimum universal rank equal to 0 and to 1.

Recommendations

• Universally optimal matrices and field independence of the minimum rank of a graph
• A note on universally optimal matrices and field independence of the minimum rank of a graph
• An upper bound for the minimum rank of a graph
• Universal adjacency matrices with two eigenvalues
• Zero forcing sets and the minimum rank of graphs

Cites work

• Combinatorial matrix theory
• Laplacian matrices of graphs: A survey
• The Gewirtz graph: An exercise in the theory of graph spectra
• The minimum rank of symmetric matrices described by a graph: a survey
• Universal adjacency matrices with two eigenvalues
• Zero forcing sets and the minimum rank of graphs

Cited in

(7)

• On the spectra and eigenspaces of the universal adjacency matrices of arbitrary lifts of graphs
• A note on universally optimal matrices and field independence of the minimum rank of a graph
• Universal adjacency matrices with two eigenvalues
• Universal spectra of the disjoint union of regular graphs
• Minimum-rank matrices with prescribed graph
• Universally optimal matrices and field independence of the minimum rank of a graph
• Perfect codes and universal adjacency spectra of commuting graphs of finite groups

This page was built for publication: The minimum rank of universal adjacency matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q448355)