Packing smaller graphs into a graph
type: Item
instance of: scholarly article
title: Packing smaller graphs into a graph
zbMATH Open document ID: 0678.05046
DOI: 10.1016/0012-365X(89)90072-1
author: Jin Akiyama
author: Fumi Nakada
author: Sinichi Tokunaga
published in: Discrete Mathematics
publication date: 1989-01-01T00:00:00Z
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. \]
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 4110738
zbMATH Keywords: m-packing number
MaRDI profile type: Publication
full work available at URL: 0012-365x(89)90072-1
OpenAlex ID: W2094837750
Recommended article: Q4340018
Recommended article: Graph packings
Recommended article: Packing of graphs with small product of sizes
Recommended article: Packing parameters in graphs
Recommended article: Packing and Squeezing Subgraphs into Planar Graphs
Recommended article: Packing in regular graphs
Recommended article: Packing graphs in their complements
Recommended article: Packing of graphs - a survey
Recommended article: Q4843030
Recommended article: Efficient subgraphs packing
description: scientific article; zbMATH DE number 4110738