Abstract
Two graphs G 1 and G 2 of order n pack if there exist injective mappings of their vertex sets into [n], such that the images of the edge sets do not intersect. Sauer and Spencer proved that if Δ (G 1) Δ (G 2) < 0.5n, then G 1 and G 2 pack. In this note, we study an Ore-type analogue of the Sauer-Spencer Theorem. Let θ(G) = max{d(u) + d(v): uv E(G)}. We show that if θ(G 1)Δ(G 2) < n, then G 1 and G 2 pack. We also characterize the pairs (G 1,G 2) of n-vertex graphs satisfying θ(G 1)Δ(G 2) = n that do not pack.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 419-424 |
| Number of pages | 6 |
| Journal | Graphs and Combinatorics |
| Volume | 23 |
| Issue number | 4 |
| DOIs | |
| State | Published - Aug 2007 |
Keywords
- Graph packing
- Ore-type conditions
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics