Algebraic connectivity of k-connected graphs

详细信息    查看全文

• 作者：Steve Kirkland ; Israel Rocha ; Vilmar Trevisan
• 关键词：algebraic connectivity ; Fiedler vector ; 05C50 ; 15A18
• 刊名：Czechoslovak Mathematical Journal
• 出版年：2015
• 出版时间：March 2015
• 年：2015
• 卷：65
• 期：1
• 页码：219-236
• 全文大小：202 KB
• 参考文献：[1] R. B. Bapat, S. J. Kirkland, S. Pati: The perturbed Laplacian matrix of a graph. Linear Multilinear Algebra 49 (2001), 219-42.View Article MATH MathSciNet
  [2] R. B. Bapat, A. K. Lal, S. Pati: On algebraic connectivity of graphs with at most two points of articulation in each block. Linear Multilinear Algebra 60 (2012), 415-32.View Article MATH MathSciNet
  [3] R. B. Bapat, S. Pati: Algebraic connectivity and the characteristic set of a graph. Linear Multilinear Algebra 45 (1998), 247-73.View Article MATH MathSciNet
  [4] N. M. M. de Abreu: Old and new results on algebraic connectivity of graphs. Linear Algebra Appl. 423 (2007), 53-3.View Article MATH MathSciNet
  [5] M. Fiedler: A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory. Czech. Math. J. 25 (1975), 619-33.MathSciNet
  [6] M. Fiedler: Algebraic connectivity of graphs. Czech. Math. J. 23 (1973), 298-05.MathSciNet
  [7] S. Kirkland: Algebraic connectivity. Handbook of Linear Algebra (L. Hogben et al., eds.). Discrete Mathematics and Its Applications, Chapman & Hall/CRC, Boca Raton, 2007, pp. 36-1-6-12.
  [8] S. Kirkland, M. Neumann, B. L. Shader: Characteristic vertices of weighted trees via Perron values. Linear Multilinear Algebra 40 (1996), 311-25.View Article MATH MathSciNet
  [9] S. Kirkland, S. Fallat: Perron components and algebraic connectivity for weighted graphs. Linear Multilinear Algebra 44 (1998), 131-48.View Article MATH MathSciNet
  [10] R. Merris: Laplacian matrices of graphs: a survey. Linear Algebra Appl. 197-98 (1994), 143-76.View Article MathSciNet
  [11] V. Nikiforov: The influence of Miroslav Fiedler on spectral graph theory. Linear Algebra Appl. 439 (2013), 818-21.View Article MATH MathSciNet
  [12] A. Pothen, H. D. Simon, K.-P. Liou: Partitioning sparse matrices with eigenvectors of graphs. SIAM J. Matrix Anal. Appl. 11 (1990), 430-52.View Article MATH MathSciNet
  
• 作者单位：Steve Kirkland (1)
  Israel Rocha (2)
  Vilmar Trevisan (2)
  
  1. Department of Mathematics, University of Manitoba, 342 Machray Hall, 186 Dysart Road, Winnipeg, MB, R3T 2N2, Canada
  2. Instituto de Matemática, Universidade Federal do Rio Grande do Sul, Avenida Bento Gon?alves, 9500, Bairro Agronomia, Porto Alegre, CEP 91509-900, Rio Grande do Sul, Brazil
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Mathematics
  Analysis
  Convex and Discrete Geometry
  Ordinary Differential Equations
  Mathematical Modeling and IndustrialMathematics
  
• 出版者：Springer Netherlands
• ISSN：1572-9141

文摘

Let G be a k-connected graph with k ?2. A hinge is a subset of k vertices whose deletion from G yields a disconnected graph. We consider the algebraic connectivity and Fiedler vectors of such graphs, paying special attention to the signs of the entries in Fielder vectors corresponding to vertices in a hinge, and to vertices in the connected components at a hinge. The results extend those in Fiedler’s papers Algebraic connectivity of graphs (1973), A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory (1975), and Kirkland and Fallat’s paper Perron Components and Algebraic Connectivity for Weighted Graphs (1998).