The minimum rank of universal adjacency matrices

DOI10.1016/J.LAA.2012.05.033zbMATH Open1252.05107arXiv1112.1718OpenAlexW1997126628WikidataQ112882197 ScholiaQ112882197MaRDI QIDQ448355FDOQ448355

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

Publication date: 6 September 2012

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

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.

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

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

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)

Cites Work

• Zero forcing sets and the minimum rank of graphs
• 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

Cited In (4)

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

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)