TY - JOUR
T1 - A hypergraph version of a graph packing theorem by Bollobás and Eldridge
AU - Kostochka, Alexandr
AU - Stocker, Christopher
AU - Hamburger, Peter
PY - 2013/10
Y1 - 2013/10
N2 - 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)|≤2n-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.
AB - 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)|≤2n-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.
KW - graph packing
KW - hypergraph
UR - http://www.scopus.com/inward/record.url?scp=84881480114&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84881480114&partnerID=8YFLogxK
U2 - 10.1002/jgt.21706
DO - 10.1002/jgt.21706
M3 - Article
AN - SCOPUS:84881480114
SN - 0364-9024
VL - 74
SP - 222
EP - 235
JO - Journal of Graph Theory
JF - Journal of Graph Theory
IS - 2
ER -