Graphs of Given Order and Size and Minimum Algebraic Connectivity

Türker Biyikoglu; Josef Leydold

doi:10.1016/j.laa.2011.09.026

Graphs of Given Order and Size and Minimum Algebraic Connectivity

Türker Biyikoglu, Josef Leydold

Publication: Working/Discussion Paper › WU Working Paper

35 Downloads (Pure)

Abstract

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 language	English
DOIs	https://doi.org/10.1016/j.laa.2011.09.026
Publication status	Published - 1 Dec 2011

Publication series

Series	Research Report Series / Department of Statistics and Mathematics
Number	115

WU Working Paper Series

Research Report Series / Department of Statistics and Mathematics

Access to Document

10.1016/j.laa.2011.09.026Licence: Unspecified

Techreport-115Final published version, 382 KBLicence: Other

Check availability

University Library Catalogue

13 Citations
1 Journal article

Graphs of given order and size and minimum algebraic connectivity
Leydold, J. & Bıyıkoğlu, T., 1 Aug 2012, In: Linear Algebra and Its Applications. 436, 7, p. 2067 - 2077
Publication: Scientific journal › Journal article › peer-review

Cite this

@techreport{c4115c3b819f46d28770da032c6edffe,

title = "Graphs of Given Order and Size and Minimum Algebraic Connectivity",

abstract = "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.",

author = "T{\"u}rker Biyikoglu and Josef Leydold",

year = "2011",

month = dec,

day = "1",

doi = "10.1016/j.laa.2011.09.026",

language = "English",

series = "Research Report Series / Department of Statistics and Mathematics",

number = "115",

type = "WorkingPaper",

}

TY - UNPB

T1 - Graphs of Given Order and Size and Minimum Algebraic Connectivity

AU - Biyikoglu, Türker

AU - Leydold, Josef

PY - 2011/12/1

Y1 - 2011/12/1

N2 - 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.

AB - 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.

U2 - 10.1016/j.laa.2011.09.026

DO - 10.1016/j.laa.2011.09.026

M3 - WU Working Paper

T3 - Research Report Series / Department of Statistics and Mathematics

BT - Graphs of Given Order and Size and Minimum Algebraic Connectivity

ER -

Graphs of Given Order and Size and Minimum Algebraic Connectivity

Abstract

Publication series

WU Working Paper Series

Access to Document

Check availability

Other versions

Graphs of given order and size and minimum algebraic connectivity

Cite this