Total interval numbers of complete r-partite graphs
Journal
Discrete Applied Mathematics
Journal Volume
122
Journal Issue
1-3
Pages
83-92
Date Issued
2002
Author(s)
Abstract
A multiple-interval representation of a graph G is a mapping f which assigns to each vertex of G a union of intervals on the real line so that two distinct vertices u and v are adjacent if and only if f(u)∩f(v)≠∅. We study the total interval number of G, defined asI(G)=min ∑ v∈V #f(v): f is a multiple-interval representation of G,where #f(v) is the minimum number of intervals whose union is f(v). We give bounds on the total interval numbers of complete r-partite graphs. Exact values are also determined for several cases. © 2002 Elsevier Science B.V.
Type
journal article