Open AccessAn Ore-type analogue of the Sauer-Spencer Theorem
Author(s) -
Alexandr Kostochka,
Gexin Yu
Publication year - 2007
Publication title -
graphs and combinatorics
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.59
H-Index - 40
eISSN - 1435-5914
pISSN - 0911-0119
DOI - 10.1007/s00373-007-0732-1
Subject(s) - mathematics , injective function , combinatorics , vertex (graph theory) , type (biology) , discrete mathematics , order (exchange) , graph , ecology , finance , economics , biology
Two graphs G1 and G2 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 Δ (G1) Δ (G2) n, then G1 and G2 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 θ(G1)Δ(G2) n, then G1 and G2 pack. We also characterize the pairs (G1,G2) of n-vertex graphs satisfying θ(G1)Δ(G2) = n that do not pack.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom