Spectral conditions for edge connectivity and spanning tree packing number in (multi-)graphs

Yang Hu, Ligong Wang, Cunxiang Duan

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)324-348
Number of pages25
JournalLinear Algebra and Its Applications
Volume664
DOIs
StatePublished - 1 May 2023

Keywords

  • Edge connectivity
  • Eigenvalue
  • Multigraph
  • Quotient matrix
  • Spanning tree packing number

Fingerprint

Dive into the research topics of 'Spectral conditions for edge connectivity and spanning tree packing number in (multi-)graphs'. Together they form a unique fingerprint.

Cite this