IEICE TRANSACTIONS on Fundamentals
Universal Graphs for Graphs with Bounded Path-Width
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 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)) .
- 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
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
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 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)) .
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 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)) .},
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 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)) .
ER -
English
