Packing smaller graphs into a graph

DOI10.1016/0012-365X(89)90072-1MaRDI QIDQ1123906zbMATH OpenOpenAlexFDO

Authors Jin Akiyama, Fumi Nakada, Sinichi Tokunaga

Publication date 1989

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365x(89)90072-1

zbMATH Keywords

m-packing number

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Review text

Let G be a connected graph and \(\alpha_ m(G)\) denote the largest number of vertex-disjoint connected subgraphs \(H_ 1,H_ 2,...,H_ k\) of G each having m vertices. The authors obtain the following bounds for the m-packing number \(\alpha_ m(G)\) for a connected graph G of order n and maximum degree \(\Delta\). \[ \lceil \frac{n-m+1}{(m-1)(\Delta -1)+1}\rceil \leq \alpha_ m(G)\leq \lfloor \frac{n}{m}\rceil. \]

Recommendations

• scientific article; zbMATH DE number 1022391
• Graph packings
• Packing of graphs with small product of sizes
• Packing parameters in graphs
• Packing and Squeezing Subgraphs into Planar Graphs
• Packing in regular graphs
• Packing graphs in their complements
• Packing of graphs - a survey
• scientific article; zbMATH DE number 786556
• Efficient subgraphs packing

Cited in

(2)

• Packing constants in graphs and connectivity
• How to Pack Directed Acyclic Graphs into Small Blocks

This page was built for publication: Packing smaller graphs into a graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1123906)