Universal Graphs for Graphs with Bounded Path-Width

Atsushi TAKAHASHI; Shuichi UENO; Yoji KAJITANI

Universal Graphs for Graphs with Bounded Path-Width

Atsushi TAKAHASHI, Shuichi UENO, Yoji KAJITANI

Full Text Views

0

Cite this

Summary :

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 F^k_n of graphs on n vertices with path-width at most k. We first show that the number of edges in a universal graph F^k_n is at least Ω(kn log(n/k)). Next, we construct a universal graph for F^k_n with O(kn log(n/k)) edges, and show that the number of edges in a minimum universal graph for F^k_n is Θ(kn log(n/k)) .

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E78-A No.4 pp.458-462

Publication Date: 1995/04/25

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)

Category

Cite this

Copy

Atsushi TAKAHASHI, Shuichi UENO, Yoji KAJITANI, "Universal Graphs for Graphs with Bounded Path-Width" in IEICE TRANSACTIONS on Fundamentals, vol. E78-A, no. 4, pp. 458-462, April 1995, doi: .
Abstract: 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 F^k_n of graphs on n vertices with path-width at most k. We first show that the number of edges in a universal graph F^k_n is at least Ω(kn log(n/k)). Next, we construct a universal graph for F^k_n with O(kn log(n/k)) edges, and show that the number of edges in a minimum universal graph for F^k_n is Θ(kn log(n/k)) .
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e78-a_4_458/_p

Copy

@ARTICLE{e78-a_4_458,
author={Atsushi TAKAHASHI, Shuichi UENO, Yoji KAJITANI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Universal Graphs for Graphs with Bounded Path-Width},
year={1995},
volume={E78-A},
number={4},
pages={458-462},
abstract={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 F^k_n of graphs on n vertices with path-width at most k. We first show that the number of edges in a universal graph F^k_n is at least Ω(kn log(n/k)). Next, we construct a universal graph for F^k_n with O(kn log(n/k)) edges, and show that the number of edges in a minimum universal graph for F^k_n is Θ(kn log(n/k)) .},
keywords={},
doi={},
ISSN={},
month={April},}

Copy

TY - JOUR
TI - Universal Graphs for Graphs with Bounded Path-Width
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 458
EP - 462
AU - Atsushi TAKAHASHI
AU - Shuichi UENO
AU - Yoji KAJITANI
PY - 1995
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E78-A
IS - 4
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - April 1995
AB - 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 F^k_n of graphs on n vertices with path-width at most k. We first show that the number of edges in a universal graph F^k_n is at least Ω(kn log(n/k)). Next, we construct a universal graph for F^k_n with O(kn log(n/k)) edges, and show that the number of edges in a minimum universal graph for F^k_n is Θ(kn log(n/k)) .
ER -