A characterization of graphs with rank 5

The rank of a graph G is defined to be the rank of its adjacency matrix. In this paper, we consider the following problem: what is the structure of a connected graph G with rank 5? or equivalently, what is the structure of a connected n-vertex graph G whose adjacency matrix has nullity n-5? In this...

Full description

Saved in:
Bibliographic Details
Published in:Linear algebra and its applications 2012-06, Vol.436 (11), p.4241-4250
Main Authors: Chang, Gerard J., Huang, Liang-Hao, Yeh, Hong-Gwa
Format: Article
Language:English
Subjects:
Adjacency matrix
Algebra
Combinatorics
Combinatorics. Ordered structures
Exact sciences and technology
Graph
Graph theory
Linear and multilinear algebra, matrix theory
Mathematics
Nullity
Rank
Sciences and techniques of general use
Spectrum
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The rank of a graph G is defined to be the rank of its adjacency matrix. In this paper, we consider the following problem: what is the structure of a connected graph G with rank 5? or equivalently, what is the structure of a connected n-vertex graph G whose adjacency matrix has nullity n-5? In this paper, we completely characterize connected graphs G whose adjacency matrix has rank 5.
ISSN:0024-3795
1873-1856
DOI:10.1016/j.laa.2012.01.021