On the minimum rank of the join of graphs and decomposable graphs

被引：19
作者：
Barioli, Francesco
Fallat, Shaun [1 ]
机构：
[1] Univ Tennessee, Dept Math, Chattanooga, TN 37403 USA
[2] Univ Regina, Dept Math & Stat, Regina, SK S4S 0A2, Canada
来源：
LINEAR ALGEBRA AND ITS APPLICATIONS | 2007年 / 421卷 / 2-3期
基金：
加拿大自然科学与工程研究理事会;
关键词：
graphs; minimum rank; maximum multiplicity; decomposable graphs; join; union; inertia-balanced; cographs;
D O I：
10.1016/j.laa.2006.05.020
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
For a given undirected graph G, the minimum rank of G is defined to be the smallest possible rank over all real symmetric matrices A whose (i, j) th entry is nonzero whenever i not equal j and {i, j} is an edge in G. In this work we consider joins and unions of graphs, and characterize the minimum rank of such graphs in the case of 'balanced inertia'. Several consequences are provided for decomposable graphs, also known as cographs. (c) 2006 Elsevier Inc. All rights reserved.
引用
收藏
页码：252 / 263
页数：12
相关论文
共 14 条
[1]  
[Anonymous], GRAPH THEORY
[2]   On the difference between the maximum multiplicity and path cover number for tree-like graphs [J].
Barioli, F ;
Fallat, S ;
Hogben, L .
LINEAR ALGEBRA AND ITS APPLICATIONS, 2005, 409 :13-31
[3]   Computation of minimal rank and path cover number for certain graphs [J].
Barioli, F ;
Fallat, S ;
Hogben, L .
LINEAR ALGEBRA AND ITS APPLICATIONS, 2004, 392 :289-303
[4]  
Barrett W, 2005, ELECTRON J LINEAR AL, V14, P32
[5]  
Barrett W, 2004, ELECTRON J LINEAR AL, V11, P258
[6]  
Bognar J., 1974, INDEFINITE INNER PRO
[7]  
FIEDLER M, 1969, LINEAR ALGEBRA APPL, V2, P191
[8]   Laplacian spectra and spanning trees of threshold graphs [J].
Hammer, PL ;
Kelmans, AK .
DISCRETE APPLIED MATHEMATICS, 1996, 65 (1-3) :255-273
[9]  
Horn R. A., 1986, Matrix analysis
[10]   On the relative position of multiple eigenvalues in the spectrum of an Hermitian matrix with a given graph [J].
Johnson, CR ;
Duarte, AL ;
Saiago, CM ;
Sutton, BD ;
Witt, AJ .
LINEAR ALGEBRA AND ITS APPLICATIONS, 2003, 363 :147-159
12