EUVIMEDEUVIMED entdecken
Crossref

A Sharp Improvement of a Theorem of Bauer and Schmeichel

Zhora Nikoghosyan

Mathematical Problems of Computer Science · 2018

DOI: 10.51408/1963-0017 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Mathematical Problems of Computer Science, 2018. Verfasst von Zhora Nikoghosyan. Die Arbeit nennt 5 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Let G be a graph on n vertices with minimum degree δ. The earliest nontrivial lower bound for the circumference c (the length of a longest cycle in G) was established in 1952 due to Dirac in terms of n and δ: (i) if G is a 2-connected graph, then c ≥ min{n, 2δ}. The bound in Theorem (i) is sharp. In 1986, Bauer and Schmeichel gave a version of this classical result for 1-tough graphs: (ii) if G is a 1-tough graph, then c ≥ min{n, 2δ + 2}. In this paper we present an improvement of (ii), which is sharp for each n: (iii) if G is a 1-tough graph, then c ≥ min{n, 2δ + 2} when n ≡ 1(mod 3); c ≥ min{n, 2δ + 3} when n ≡ 2(mod 3) or n ≡ 1(mod 4); and c ≥ min{n, 2δ + 4} otherwise.

Zitieren

APA

Nikoghosyan, Z. (2018). A Sharp Improvement of a Theorem of Bauer and Schmeichel. Mathematical Problems of Computer Science. https://doi.org/10.51408/1963-0017

Vancouver

Nikoghosyan Z. A Sharp Improvement of a Theorem of Bauer and Schmeichel. Mathematical Problems of Computer Science. 2018. doi:10.51408/1963-0017

BibTeX
@article{Nikoghosyan2018,
  author = {Nikoghosyan, Zhora},
  title = {A Sharp Improvement of a Theorem of Bauer and Schmeichel},
  journal = {Mathematical Problems of Computer Science},
  year = {2018},
  doi = {10.51408/1963-0017}
}
Kostenlos starten →