✦ LIBER ✦

Packing smaller graphs into a graph

✍ Scribed by Jin Akiyama; Fumi Nakada; Sinichi Tokunaga

Publisher: Elsevier Science
Year: 1989
Tongue: English
Weight: 117 KB
Volume: 75
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(89)90072-1

No coin nor oath required. For personal study only.

✦ Synopsis

Let G be a graph. Given an integer m < IV(G)l, we obtain a lower bound for the largest number of vertex-disjoint subgraphs of G, each of which has m vertices.

📜 SIMILAR VOLUMES

Packing two bipartite graphs into a comp

Packing two bipartite graphs into a complete bipartite graph

✍ Wang, Hong 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 131 KB 👁 3 views

For two integers a and b, we say that a bipartite graph G admits an (a, b)bipartition if G has a bipartition (X, Y ) such that |X| = a and |Y | = b. We say that two bipartite graphs G and H are compatible if, for some integers a and b, both G and H admit (a, b)-bipartitions. In this paper, we prove

Packing trees into planar graphs

✍ A. García; C. Hernando; F. Hurtado; M. Noy; J. Tejel 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 108 KB

## Abstract In this study, we provide methods for drawing a tree with __n__ vertices on a convex polygon, without crossings and using the minimum number of edges of the polygon. We apply the results to obtain planar packings of two trees in some specific cases. © 2002 Wiley Periodicals, Inc. J Grap

Packing two forests into a bipartite gra

Packing two forests into a bipartite graph

✍ Wang, Hong 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 292 KB 👁 3 views

For two integers a and b, we say that a bipartite graph G admits an ( a , b)-bipartition if G has a bipartition ( X , Y ) such that /XI = a and ( Y / = b. We say that two bipartite graphs G and H are compatible if, for some integers a and b, both G and H admit ( a , b)-bipartitions. In this note, w

Clique graphs of packed graphs

✍ Iwao Sato 📂 Article 📅 1986 🏛 Elsevier Science 🌐 English ⚖ 129 KB

Let IGI be the number of vertices of a graph G and to(G) be the density of G. We call a graph G packed if the clique graph K(G) of G has exactly 2 IGI-O'(G) cliques. We correct the characterization of clique graphs of packed graphs given in Theorem 3.2 of Hedman [3]. All graphs considered here are f

Packing two copies of a sparse graph int

Packing two copies of a sparse graph into a graph with restrained maximum degree

✍ Hong Wang 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 132 KB

## Abstract We show that if a tree __T__ is not a star, then there is an embedding σ of __T__ in the complement of __T__ such that the maximum degree of __T__∪σ(__T__) is at most Δ(__T__)+2. We also show that if __G__ is a graph of order __n__ with __n__−1 edges, then with several exceptions, there

Packing almost stars into the complete g

Packing almost stars into the complete graph

✍ Dobson, Edward 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 79 KB 👁 2 views

We verify that the Tree Packing Conjecture is true for all sequences of trees T 1 , . . . , T n such that there exists x i ∈ V (T i ) and T i -x i has at least i -6(i -1)/4 isolated vertices.