Packing in honeycomb networks
type: Item
instance of: scholarly article
title: Packing in honeycomb networks
zbMATH Open document ID: 1407.05197
author: Indra Rajasingh
author: Muthumalai
author: A. S. Shanthi
author: R. Bharati
publication date: 2012-10-11T00:00:00Z
review text: An \(H\)-packing of a graph \(G\) is a set of vertex disjoint subgraphs of \(G\), each of which is isomorphic to a fixed graph \(H\). The packing number, denoted as \(\lambda(G,H)\), is then defined as the maximum number of vertex disjoint copies of \(H\) in \(G\). Moreover, an \(H\)-packing is called perfect if it covers all vertices of \(G\). It is obvious that when \(H=K_2\), the problem of determining the packing number becomes the maximum matching problem. In the present paper, authors study various packings for a special family of important chemical graphs known as honeycomb networks (which belong to the well known family of benzenoid graphs). In particular, the family of graphs \(HC(n)\), \(n \geq 1\), is defined in the following way: \(HC(1)\) is just a hexagon and \(HC(n)\) is obtained from \(HC(n-1)\) by adding a layer of hexagons around the boundary of \(HC(n-1)\). Note that the graphs \(HC(n)\) are also called coronenes or circumcoronenes. In Section 3, it is shown that there exists a perfect \(P_6\)-packing of \(HC(n)\) with \(n^2\) copies of \(P_6\). In the next section, an algorithm is described to pack \(HC(n)\) with \(C_6\) and therefore, a lower bound for \(\lambda(HC(n),C_6)\) is obtained. Moreover, the packing of a honeycomb torus network with copies of \(C_6\) is investigated in Section 5, and an algorithm for a \(K_{1,3}\)-packing of \(HC(n)\) is developed in Section 6. Finally, in the last section a procedure for an \(H\)-packing of \(HC(n)\) is described where \(H\) is a \(1,3\)-dimethyl cyclohexane.
reviewed by: Niko Tratnik
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 92E10
Mathematics Subject Classification ID: 05C82
Mathematics Subject Classification ID: 05C90
zbMATH DE Number: 6092932
zbMATH Keywords: \(H\)-packing
zbMATH Keywords: perfect packing
zbMATH Keywords: honeycomb network
zbMATH Keywords: benzenoid graph
zbMATH Keywords: matching
MaRDI profile type: Publication
full work available at URL: s10910-011-9962-9
OpenAlex ID: W1993405918
cites work: Q4829009
cites work: Packing almost stars into the complete graph
cites work: Packing lines in a hypercube
cites work: On the completeness of a generalized matching problem
cites work: A Generalized Parity Function and Its Use in the Construction of Perfect Codes
cites work: Optimal packing of induced stars in a graph
cites work: An extension of Tutte's 1-factor theorem
cites work: Packing of graphs - a survey
DOI: 10.1007/S10910-011-9962-9
published in: Journal of Mathematical Chemistry
description: scientific article; zbMATH DE number 6092932