The inertia set of a signed graph

被引:11
作者
Arav, Marina [1 ]
Hall, Frank J. [1 ]
Li, Zhongshan [1 ,2 ]
van der Holst, Hein [1 ]
机构
[1] Georgia State Univ, Dept Math & Stat, Atlanta, GA 30303 USA
[2] North Univ China, Dept Math, Taiyuan 030051, Shanxi, Peoples R China
关键词
Graph; Signed graph; Inertia; Symmetric; Minor; SPECTRAL CHARACTERIZATION; MINIMUM RANK;
D O I
10.1016/j.laa.2013.04.032
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
A signed graph is a pair (G, Sigma), where G = (V, E) is a graph (in which parallel edges are permitted, but loops are not) with V = {1, ..., n} and Sigma subset of E. The edges in Sigma are called odd edges and the other edges of E even. By S(G, Sigma) we denote the set of all symmetric V x V matrices A = [a(i,j)] with a(i,j) < 0 if i and j are adjacent and all edges between i and j are even, a(i,j) > 0 if i and j are adjacent and all edges between i and j are odd, a(i,j) is an element of R if i and j are connected by even and odd edges, a(i,j) = 0 if i not equal j and i and j are non-adjacent, and a(i,j) is an element of R for all vertices i. The stable inertia set of a signed graph (G, Sigma) is the set of all pairs (p, q) for which there exists a matrix A is an element of S(G, Sigma) with p positive and q negative eigenvalues which has the Strong Arnold Property. In this paper, we study the stable inertia set of (signed) graphs. (C) 2013 Elsevier Inc. All rights reserved.
引用
收藏
页码:1506 / 1529
页数:24
相关论文
共 18 条
  • [1] Barioli F, 2005, ELECTRON J LINEAR AL, V13, P387
  • [2] Barrett W, 2004, ELECTRON J LINEAR AL, V11, P258
  • [3] The inverse inertia problem for graphs: Cut vertices, trees, and a counterexample
    Barrett, Wayne
    Hall, H. Tracy
    Loewy, Raphael
    [J]. LINEAR ALGEBRA AND ITS APPLICATIONS, 2009, 431 (08) : 1147 - 1191
  • [4] Colin de Verdiere Y., 1993, Graph Structure Theory, P137
  • [5] de Verdiere YC, 1998, J COMB THEORY B, V74, P121
  • [6] NEW INVARIANT OF GRAPHS AND FLATNESS CRITERION
    DEVERDIERE, YC
    [J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 1990, 50 (01) : 11 - 21
  • [7] Diestel R., 2000, Graph Theory
  • [8] The minimum rank of symmetric matrices described by a graph: A survey
    Fallat, Shaun M.
    Hogben, Leslie
    [J]. LINEAR ALGEBRA AND ITS APPLICATIONS, 2007, 426 (2-3) : 558 - 582
  • [9] Fiedler M., 1969, LINEAR ALGEBRA APPL, V2, P191, DOI [10.1016/0024-3795(69)90027-5, DOI 10.1016/0024-3795(69)90027-5]
  • [10] Haynsworth E. V., 1968, LINEAR ALGEBRA APPL, V1, P73, DOI [10.1016/0024-3795(68)90050-5, DOI 10.1016/0024-3795(68)90050-5]