## Mathematics Faculty Articles

#### Title

The Minimum Rank of Universal Adjacency Matrices

#### Document Type

Article

#### Publication Date

10-15-2012

#### Publication Title

Linear Algebra and its Applications

#### Keywords

Adjacency matrix, Universal adjacency matrix, Laplacian matrix, Minimum rank, Graph, Path, Cycle

#### ISSN

0024-3795

#### Volume

437

#### Issue/No.

8

#### First Page

2064

#### Last Page

2076

#### Abstract

In this paper we introduce a new parameter for a graph called the *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(α,β,γ,δ)=αA+βI+γJ+δDU(α,β,γ,δ)=αA+βI+γJ+δ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 α≠0,β,γ,δ 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.

#### NSUWorks Citation

Ahmadi, B.; Alinaghipour, F.; Fallat, Shaun M.; Fan, Yi-Zheng; Meagher, K.; and Nasserasr, Shahla, "The Minimum Rank of Universal Adjacency Matrices" (2012). *Mathematics Faculty Articles*. 120.

https://nsuworks.nova.edu/math_facarticles/120

#### DOI

10.1016/j.laa.2012.05.033

COinS

## Comments

Under an Elsevier user license

## AMS classification