TY - JOUR
T1 - Spectral conditions for edge connectivity and spanning tree packing number in (multi-)graphs
AU - Hu, Yang
AU - Wang, Ligong
AU - Duan, Cunxiang
N1 - Publisher Copyright:
© 2023 Elsevier Inc.
PY - 2023/5/1
Y1 - 2023/5/1
N2 - A multigraph is a graph with possible multiple edges, but no loops. Let t be a positive integer. Let Gt be the set of simple graphs (or multigraphs) such that for each G∈Gt there exist at least t+1 non-empty disjoint proper subsets V1,V2,…,Vt+1⊆V(G) satisfying V(G)∖(V1∪V2∪⋯∪Vt+1)≠ϕ and edge connectivity κ′(G)=e(Vi,V(G)∖Vi) for i=1,2,…,t+1. Let D(G) and A(G) denote the degree diagonal matrix and adjacency matrix of a simple graph (or a multigraph) G, and let μi(G) be the ith largest eigenvalue of the Laplacian matrix L(G)=D(G)+A(G). In this paper, we investigate the relationship between μn−2(G) and edge connectivity or spanning tree packing number of a graph G∈G1, respectively. We also give the relationship between μn−3(G) and edge connectivity or spanning tree packing number of a graph G∈G2, respectively. Moreover, we generalize all the results about L(G) to a more general matrix aD(G)+A(G), where a is a real number with a≥−1.
AB - A multigraph is a graph with possible multiple edges, but no loops. Let t be a positive integer. Let Gt be the set of simple graphs (or multigraphs) such that for each G∈Gt there exist at least t+1 non-empty disjoint proper subsets V1,V2,…,Vt+1⊆V(G) satisfying V(G)∖(V1∪V2∪⋯∪Vt+1)≠ϕ and edge connectivity κ′(G)=e(Vi,V(G)∖Vi) for i=1,2,…,t+1. Let D(G) and A(G) denote the degree diagonal matrix and adjacency matrix of a simple graph (or a multigraph) G, and let μi(G) be the ith largest eigenvalue of the Laplacian matrix L(G)=D(G)+A(G). In this paper, we investigate the relationship between μn−2(G) and edge connectivity or spanning tree packing number of a graph G∈G1, respectively. We also give the relationship between μn−3(G) and edge connectivity or spanning tree packing number of a graph G∈G2, respectively. Moreover, we generalize all the results about L(G) to a more general matrix aD(G)+A(G), where a is a real number with a≥−1.
KW - Edge connectivity
KW - Eigenvalue
KW - Multigraph
KW - Quotient matrix
KW - Spanning tree packing number
UR - http://www.scopus.com/inward/record.url?scp=85147606198&partnerID=8YFLogxK
U2 - 10.1016/j.laa.2023.01.022
DO - 10.1016/j.laa.2023.01.022
M3 - 文章
AN - SCOPUS:85147606198
SN - 0024-3795
VL - 664
SP - 324
EP - 348
JO - Linear Algebra and Its Applications
JF - Linear Algebra and Its Applications
ER -