The search functionality is under construction.

Keyword Search Result

[Keyword] universal graph(1hit)

1-1hit
  • Universal Graphs for Graphs with Bounded Path-Width

    Atsushi TAKAHASHI  Shuichi UENO  Yoji KAJITANI  

     
    PAPER

      Vol:
    E78-A No:4
      Page(s):
    458-462

    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)) .