TY - JOUR
T1 - Total Interval Number for Graphs with Bounded Degree
AU - Kostochka, Alexander V.
AU - West, Douglas B.
N1 - Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.
PY - 1997/5
Y1 - 1997/5
N2 - 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.
AB - 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.
KW - Intersection representation
KW - Maximum degree
KW - Total interval number
UR - http://www.scopus.com/inward/record.url?scp=0031527478&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0031527478&partnerID=8YFLogxK
U2 - 10.1002/(SICI)1097-0118(199705)25:1<79::AID-JGT5>3.0.CO;2-F
DO - 10.1002/(SICI)1097-0118(199705)25:1<79::AID-JGT5>3.0.CO;2-F
M3 - Article
AN - SCOPUS:0031527478
SN - 0364-9024
VL - 25
SP - 79
EP - 84
JO - Journal of Graph Theory
JF - Journal of Graph Theory
IS - 1
ER -