Star complements and edge-connectivity in finite graphs

Citation

Rowlinson P (2015) Star complements and edge-connectivity in finite graphs. Linear Algebra and Its Applications, 476, pp. 124-132. https://doi.org/10.1016/j.laa.2015.03.003

Abstract
Let G be a finite graph with H as a star complement for a non-zero eigenvalue μ. Let κ'(G), δ(G) denote respectively the edge-connectivity and minimum degree of G. We show that κ'(G) is controlled by δ(G) and κ'(H). We describe the possibilities for a minimum cutset of G when μ∉{-1,0}. For such μ, we establish a relation between κ'(G) and the spectrum of H when G has a non-trivial minimum cutset E⊈E(H).

Keywords
graph; connectivity; eigenvalue; star complement

Journal
Linear Algebra and Its Applications: Volume 476

People

Professor Peter Rowlinson

Emeritus Professor, Mathematics