dc.identifier.uri |
http://dx.doi.org/10.15488/2709 |
|
dc.identifier.uri |
http://www.repo.uni-hannover.de/handle/123456789/2735 |
|
dc.contributor.author |
Kriesell, Matthias
|
|
dc.date.accessioned |
2018-01-29T14:34:09Z |
|
dc.date.available |
2018-01-29T14:34:09Z |
|
dc.date.issued |
2005 |
|
dc.identifier.citation |
Kriesell, M.: Triangle density and contractibility. In: Combinatorics, Probability and Computing 14 (2005), Nr. 1-2, S. 133-146. DOI: https://doi.org/10.1017/S0963548304006601 |
|
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 |
eng |
dc.type |
Article |
|
dc.type |
Text |
|
dc.relation.issn |
0963-5483 |
|
dc.relation.doi |
https://doi.org/10.1017/S0963548304006601 |
|
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 |
|