Graphs of given order and size and minimum algebraic connectivity

Josef Leydold, Türker Bıyıkoğlu

Publication: Scientific journalJournal articlepeer-review


The structure of connected graphs of given size and order that have minimal algebraic connectivity is investigated. It is shown that they must consist of a chain of cliques.
Moreover, an upper bound for the number of maximal cliques of size 2 or larger is derived.
Original languageEnglish
Pages (from-to)2067 - 2077
JournalLinear Algebra and Its Applications
Issue number7
Publication statusPublished - 1 Aug 2012

Cite this