Two theorems on packings of graphs
From MaRDI portal
Two graphs G, H of the same order are called packable if G can be embedded in the complement \(\bar H\) of H. The main results of the present paper: Theorem 1 states that two non-star graphs of order \(p\geq 5\) and size p-1 are packable with exception of specified 13 pairs. Theorem 2 gives a complete characterization when a tree on p vertices and a graph of order p size p form a couple of packable graphs. This represents a generalization of various known results by Sauer, Spencer, Burns, Schuster, Slater and the authors.
Recommendations
Cites work
- Edge disjoint placement of graphs
- Embedding (p,p - 1) graphs in their complements
- Embedding graphs in their complements
- Every (p,p-2) graph is contained in its complement
- scientific article; zbMATH DE number 3652373 (Why is no real title available?)
- scientific article; zbMATH DE number 3771651 (Why is no real title available?)
- scientific article; zbMATH DE number 3290993 (Why is no real title available?)
- Packing a tree with a graph of the same size
- Packings of graphs and applications to computational complexity
- Subgraphs of graphs. I
Cited in
(31)- On packing bipartite graphs
- Packing of graphs and permutations -- a survey
- Packing graphs in their complements
- Packing without some pieces
- Packing two graphs of even girth 10
- Sparse graphs of girth at least five are packable
- Packing of graphs - a survey
- Packing a tree of order p with a (p,p+1)-graph
- On asymptotic packing of geometric graphs
- Packing three copies of a tree into its sixth power
- A note on packing graphs without cycles of length up to five
- Labeled embedding of \((n, n-2)\)-graphs in their complements
- Two theorems on graphs
- A hypergraph version of a graph packing theorem by Bollobás and Eldridge
- The packing number and Laplacian spectrum of a graph
- Packing a tree with a graph of the same size
- scientific article; zbMATH DE number 4127266 (Why is no real title available?)
- scientific article; zbMATH DE number 554182 (Why is no real title available?)
- scientific article; zbMATH DE number 731858 (Why is no real title available?)
- scientific article; zbMATH DE number 790422 (Why is no real title available?)
- A note on careful packing of a graph
- Incidence dimension and 2-packing number in graphs
- An Improvement in the Two-packing Bound Related to Vizing's Conjecture
- On packable digraphs
- A note on packing of two copies of a hypergraph
- Packing of any set of graphs into a graceful / harmonious / elegant graph.
- On Two Conjectures on Packing of Graphs
- On asymptotic packing of convex geometric and ordered graphs
- A short proof that the list packing number of any graph is well defined
- Packing of the k-power of Hamilton cycles
- Packing two graphs of order n having total size at most 2n-2
This page was built for publication: Two theorems on packings of graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1090341)
