Graph toughness from Laplacian eigenvalues

Xiaofeng Gu*, W. H. Haemers

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

11 Citations (Scopus)

Abstract

The toughness t(G) of a graph G = (V, E) is defined as (Equation presented), in which the minimum is taken over all S ⊂ V such that G − S is disconnected, where c(G − S) denotes the number of components of G − S. We present two tight lower bounds for t(G) in terms of the Laplacian eigenvalues and provide strong support for a conjecture for a better bound which, if true, implies both bounds, and improves and generalizes known bounds by Alon, Brouwer, and the first author. As applications, several new results on perfect matchings, factors and walks from Laplacian eigenvalues are obtained, which leads to a conjecture about Hamiltonicity and Laplacian eigenvalues.
Original languageEnglish
Pages (from-to)53-61
JournalAlgebraic Combinatorics
Volume5
Issue number1
DOIs
Publication statusPublished - Jan 2022

Keywords

  • Hamilton cycle
  • Laplacian eigenvalue
  • Toughness
  • factor
  • perfect matching

Fingerprint

Dive into the research topics of 'Graph toughness from Laplacian eigenvalues'. Together they form a unique fingerprint.

Cite this