Premium
A Hypergraph Version of a Graph Packing Theorem by Bollobás and Eldridge
Author(s) -
Kostochka Alexandr,
Stocker Christopher,
Hamburger Peter
Publication year - 2013
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21706
Subject(s) - combinatorics , mathematics , vertex (graph theory) , bijection , hypergraph , discrete mathematics , graph
Two n ‐vertex hypergraphs G and H pack , if there is a bijection f : V ( G ) → V ( H ) such that for every edge e ∈ E ( G ) , the set { f ( v ) : v ∈ e } is not an edge in H . Extending a theorem by Bollobás and Eldridge on graph packing to hypergraphs, we show that if n ≥ 10 and n ‐vertex hypergraphs G and H with | E ( G ) | + | E ( H ) | ≤ 2 n − 3 with no edges of size 0, 1, n − 1 and n do not pack, then either one of G and H contains a spanning graph‐star, and each vertex of the other is contained in a graph edge, or one of G and H has n − 1 edges of size n − 2 not containing a given vertex, and for every vertex x of the other hypergraph some edge of size n − 2 does not contain x .