Graph representations using stars, trees, intervals and boxes

We introduce star number (tree number) of a graph G, which is the minimum t such that G is the intersection graph of unions of t substars (subtrees) of a host tree. We characterize the graphs with star number 1 and prove that a planar graph has star number at most 3. We study bounds on these two parameters and compare them with interval number. We prove that the star number is at most $\lceil(n + 1)/4\rceil,$ where n is the number of vertices. We also show the independence of interval number and star number.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Mathematics

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2011

Author dc:creator

• Chang, Yi-Wu

Contributors dc:contributor

• Weischel, Paul W.

• Mathematics

Statement dc:rights

• Copyright 1994 Chang, Yi-Wu

Language dc:language

eng

Identifier

AAI9512323
(UMI)AAI9512323

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/21303