Premium
Total interval number for graphs with bounded degree
Author(s) -
Kostochka Alexander V.,
West Douglas B.
Publication year - 1997
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(199705)25:1<79::aid-jgt5>3.0.co;2-f
Subject(s) - mathematics , combinatorics , discrete mathematics , graph , bounded function , degree (music) , interval graph , interval (graph theory) , vertex (graph theory) , line graph , pathwidth , acoustics , mathematical analysis , physics
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. © 1997 John Wiley & Sons, Inc. J Graph Theory 25: 79–84, 1997