On the unit interval number of a graph

Link:
Autor/in:
Erscheinungsjahr:
1988
Medientyp:
Text
Schlagworte:
  • Article
  • Article
Beschreibung:
  • The unit interval number of a simple undirected graph G, denoted iu(G), is the least nonnegative integer r for which we can assign to each vertex in G a collection of at most r closed unit intervals on the real line such that two distinct vertices v and w of G are adjacent if and only if some interval for v intersects some interval for w. This concept generalizes the notion of a unit interval graph in the same way as the previously studied interval number generalizes the notion of an interval graph. We present the following results on the unit interval number. Let G be a graph on n vertices. Then . For even n, the extremal graphs are K1,n−1 and C4. For odd n≥3, the extremal graphs are C5, those graphs which contain induced copies of K1,n−2 and (if n=5) those graphs with an induced C4. These results suggest the question whether the unit interval number is unbounded for claw-free graphs, which we answer in the affirmative. On the other hand, we find that iu(G)≤3 when G is the complement of a forest. In addition, we also present an upper bound on iu(G) in terms of the edge number of G, together with a characterization of the corresponding extremal graphs.
Lizenz:
  • info:eu-repo/semantics/openAccess
Quellsystem:
Forschungsinformationssystem der UHH

Interne Metadaten
Quelldatensatz
oai:www.edit.fis.uni-hamburg.de:publications/9ec299aa-9e34-4b0a-9eb9-c2109d4eb0a4