Topics in Intersection Graphs
Date Issued
2008
Date
2008
Author(s)
Li, Bo-Jr
Abstract
This dissertation focuses on the study of three topics in intersection graph theory:lique coverings (partitions) of graphs, dot product representations of graphs and competition graphs.e first study clique coverings (partitions) of line graphs in Chapter 2. This chapter gives alternative proofs, using a unified approach, for the results on the clique covering (partition) numbers of line graphs obtained bycGuinness and Rees [41].e also employ the proof techniques to give an alternative proof for the De Brujin-ErdH{o}s Theorem.e next study the dot product representation problem, which was introduced by Fiduccia et al. [16] in 1998, in Chapters 3 and 4. They showed that $o(K_{n,n})=n$ and conjectured that for all graphs G of n vertices,$o(G)leqfrac{n}{2}$. Chapter 3 gives partial solutions to this conjecture.e then define the closely related notions of (strict) strong dot product representation. Chapter 4 studies (strict) strong dot product representations.inally, we investigate the competition graphs in Chapters 5 through 8.oberts [50] proved that the competition number of chordal graph is at most one. Cho and Kim [8] established that the competition number of a graph with exactly one hole is at most two. Given two positive integers h and k with $kleq h+1$, Kim [30] constructed a connected graph G with exactly h holes and $kappa(G)=k$.hen he asked the question: Is h+1 the maximum competition number of a graph with exactly $h$ holes? The answer is yes for $hleq 1$. We first show that the competition number of a graph with exactly h holes, all of which are independent, is at most h+1 in Chapter 5. Next, Chapter 6 proves the answer of this question is yes for h=2.n Chapter 7, we review some results on domination graphs of tournaments. We characterize a tournament that satisfies the empty-to-complete property. We also study coloring on -domination graphs of tournaments. Chapter 8 studies coloring on competition graphs and competition hypergraphs of tournaments.
Subjects
clique coverings (partitions)
dot product representations
competition graphs
independent hole
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-97-D92221003-1.pdf
Size
23.53 KB
Format
Adobe PDF
Checksum
(MD5):3be1fe81143cdc4d5c7e43d5ab0e96ed