Lower bounds for locally highly connected graphs

Adamaszek, Anna; Adamaszek, Michal; Mnich, Matthias; Schmidt, Jens M.

Lower bounds for locally highly connected graphs

Basic Data Publication

Publikationstyp

Journal Article

Date Issued

2016-02-18

Sprache

English

Author(s)

TORE-URI

http://hdl.handle.net/11420/4551

Publisher Version

Journal

Graphs and combinatorics

Volume

32

Start Page

1641

End Page

1650

Citation

Graphs and Combinatorics 32 : 1641-1650 (2016)

Publisher DOI

10.1007/s00373-016-1686-y

Publisher

Springer

Abstract

We propose a conjecture regarding the lower bound for the number of edges in locally k-connected graphs and we prove it for \(k=2\). In particular, we show that every connected locally 2-connected graph is \(M_3\)-rigid. For the special case of surface triangulations, this fact was known before using topological methods. We generalize this result to all locally 2-connected graphs and give a purely combinatorial proof. Our motivation to study locally k-connected graphs comes from lower bound conjectures for flag triangulations of manifolds, and we discuss some more specific problems in this direction.

Content

DDC Class

004: Informatik