Universal Graphs for Graphs with Bounded Path-Width

Atsushi TAKAHASHI  Shuichi UENO  Yoji KAJITANI  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E78-A   No.4   pp.458-462
Publication Date: 1995/04/25
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
universal graph,  path-width,  k-path,  parallel computing,  

Full Text: PDF>>
Buy this Article

A graph G is said to be universal for a family F of graphs if G contains every graph in F as a subgraph. A minimum universal graph for F is a universal graph for F with the minimum number of edges. This paper considers a minimum universal graph for the family Fkn of graphs on n vertices with path-width at most k. We first show that the number of edges in a universal graph Fkn is at least Ω(kn log(n/k)). Next, we construct a universal graph for Fkn with O(kn log(n/k)) edges, and show that the number of edges in a minimum universal graph for Fkn is Θ(kn log(n/k)) .