Eintrag weiter verarbeiten
A sharp lower bound for the circumference of 1‐tough graphs with large degree sums
Gespeichert in:
Personen und Körperschaften: | |
---|---|
Titel: |
A sharp lower bound for the circumference of 1‐tough graphs with large degree sums |
In: | Journal of Graph Theory, 20, 1995, 2, S. 137-140 |
veröffentlicht: |
Wiley
|
Umfang: | 137-140 |
ISSN: |
0364-9024 1097-0118 |
DOI: | 10.1002/jgt.3190200204 |
Zusammenfassung: | <jats:title>Abstract</jats:title><jats:p>We show that every 1‐tough graph <jats:italic>G</jats:italic> on <jats:italic>n</jats:italic> ≥ 3 vertices with σ<jats:sub>3</jats:sub>≧ <jats:italic>n</jats:italic> has a cycle of length at least min{<jats:italic>n, n</jats:italic> + (σ<jats:sub>3</jats:sub>/3 ) − α + 1}, where σ<jats:sub>3</jats:sub> denotes the minimum value of the degree sum of any 3 pairwise nonadjacent vertices and α the cardinality of a miximum independent set of vertices in <jats:italic>G</jats:italic>. Our inequality is sharp and implies some sufficient conditions of hamiltonian cycles. © 1995 John Wiley & Sons, Inc.</jats:p> |
Format: | E-Article |
Quelle: | Wiley (CrossRef) |
Sprache: | Englisch |