Total Interval Number for Graphs with Bounded Degree

Alexander V. Kostochka, Douglas B. West

Research output: Contribution to journalArticlepeer-review

Abstract

The total interval number of an n-vertex graph with maximum degree Δ is at most (Δ + 1/Δ)n/2, with equality if and only if every component of the graph is KΔ,Δ. If the graph is also required to be connected, then the maximum is Δn/2 + 1 when Δ is even, but when Δ is odd it exceeds [Δ + 1/(2.5Δ + 7.7)]n/2 for infinitely many n.

Original languageEnglish (US)
Pages (from-to)79-84
Number of pages6
JournalJournal of Graph Theory
Volume25
Issue number1
DOIs
StatePublished - May 1997
Externally publishedYes

Keywords

  • Intersection representation
  • Maximum degree
  • Total interval number

ASJC Scopus subject areas

  • Geometry and Topology

Fingerprint Dive into the research topics of 'Total Interval Number for Graphs with Bounded Degree'. Together they form a unique fingerprint.

Cite this