A Near Packing of Two Graphs

✍ Scribed by Nancy Eaton

• Publisher: Elsevier Science
• Year: 2000
• Tongue: English
• Weight: 99 KB
• Volume: 80
• Category: Article
• ISSN: 0095-8956
• DOI: 10.1006/jctb.2000.1971

✦ Synopsis

Let G 1 and G 2 be two graphs on n vertices with 2(G 1 )=d 1 and 2(G 2 )=d 2 . A packing of G 1 and G 2 is a set

and H 1 and H 2 are edge disjoint subgraphs of K n . B. Bolloba s and S. E. Eldridge (1978, J. Combin. Theory Ser. B 25, 105 124) made the following conjecture. If (d 1 +1) } (d 1 +1) n+1, then there is a packing of G 1 and G 2 . The degree condition stated in this conjecture could not be weakened, since there exist two such graphs for which (d 1 +1) } (d 2 +1)=n+2, and no packing is possible. N. Sauer and J. Spencer (1978, J. Combin. Theory Ser. B 25, 295 302

2 n then there is a packing of G 1 and G 2 . In this paper, a generalization and extension of the Sauer Spencer result is proven. We define a near packing of degree d of two graphs of order n as a generalization of a packing. In a near packing of degree d, the copies of the two graphs may overlap so that the maximum degree of the subgraph defined by the edges common to both copies is d. Thus a near packing of degree 0 is a packing. The result can then be stated as follows. Let a # R + . If d 1 } d 2 an, then there exists a near packing of degree d of G 1 and G 2 for some d<2a. Furthermore, if (d 1 +1) } (d 2 +1) n+1, then the maximum degree d of the subgraph defined by the edges common to both the copy of G 1 and the copy of G 2 is at most 1 and its size is no larger than n 2 +1&d 1 &d 2 .

2000 Academic Press Definition 1.1. Let G 1 and G 2 be two graphs such that, |V(G

In 1978, Bolloba s and Eldridge [2] made the following conjecture. Conjecture 1. If |V(G 1 )| = |V(G 2 )| =n and (2(G 1 )+1) } (2(G 2 )+1) n+1, then there is a packing of G 1 and G 2 .