The rank of a graph after vertex addition

Let r( G) denote the rank of the adjacency matrix of a graph G. When a vertex and its incident edges are deleted from G, the rank of the resultant graph cannot exceed r( G) and can decrease by at most 2. The problem of determining the exact effect of adding a single vertex to a graph is more difficu...

Full description

Saved in:
Bibliographic Details
Published in:Linear algebra and its applications 1997-11, Vol.265 (1), p.55-69
Main Authors: Bevis, Jean H., Blount, Kevin K., Davis, George J., Domke, Gayla S., Miller, Valerie A.
Format: Article
Language:English
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:Let r( G) denote the rank of the adjacency matrix of a graph G. When a vertex and its incident edges are deleted from G, the rank of the resultant graph cannot exceed r( G) and can decrease by at most 2. The problem of determining the exact effect of adding a single vertex to a graph is more difficult, since the number of edges that can be added with this vertex is variable. The rank of the new graph cannot decrease and it can increase by at most 2. We obtain results examining several cases of vertex addition.
ISSN:0024-3795
1873-1856
DOI:10.1016/S0024-3795(96)00513-7