Show simple item record

dc.identifier.uri Kriesell, Matthias 2018-01-29T14:34:09Z 2018-01-29T14:34:09Z 2005
dc.identifier.citation Kriesell, M.: Triangle density and contractibility. In: Combinatorics, Probability and Computing 14 (2005), Nr. 1-2, S. 133-146. DOI:
dc.description.abstract Let G be a noncomplete k -connected graph such that the graphs obtained from contracting any edge in G are not k-connected, and let t(G) denote the number of triangles in G. Thomassen proved t(G) ≥ 1, which was later improved by Mader to t(G) ≥ 1/3|V(G)|. Here we show t(G) ≥ 2/3|V(G)| (which is best possible in general). Furthermore it is proved that, for k ≥ 4, a k-connected graph without two disjoint triangles must contain an edge not contained in a triangle whose contraction yields a k-connected graph. As an application, for k ≥ 4 every k-connected graph G admits two disjoint induced cycles C1, C2 such that G - V(C1) and G - V(C2) are (k - 3)-connected. eng
dc.language.iso eng
dc.publisher Cambridge : Cambridge University Press
dc.relation.ispartofseries Combinatorics, Probability and Computing 14 (2005), Nr. 1-2
dc.rights Es gilt deutsches Urheberrecht. Das Dokument darf zum eigenen Gebrauch kostenfrei genutzt, aber nicht im Internet bereitgestellt oder an Außenstehende weitergegeben werden. Dieser Beitrag ist aufgrund einer (DFG-geförderten) Allianz- bzw. Nationallizenz frei zugänglich.
dc.subject Computational complexity eng
dc.subject Computational methods eng
dc.subject Large scale systems eng
dc.subject Problem solving eng
dc.subject Set theory eng
dc.subject Theorem proving eng
dc.subject Clique size eng
dc.subject Connectivity theory eng
dc.subject Nonisomorphic contraction eng
dc.subject Triangle density eng
dc.subject Combinatorial mathematics eng
dc.subject.ddc 510 | Mathematik ger
dc.title Triangle density and contractibility
dc.type article
dc.type Text
dc.relation.issn 0963-5483
dc.bibliographicCitation.issue Februar
dc.bibliographicCitation.volume 14
dc.bibliographicCitation.firstPage 133
dc.bibliographicCitation.lastPage 146
dc.description.version publishedVersion
tib.accessRights frei zug�nglich

Files in this item

This item appears in the following Collection(s):

Show simple item record


Search the repository


My Account

Usage Statistics