The generalized hierarchical product of graphs

A generalization of both the hierarchical product and the Cartesian product of graphs is introduced and some of its properties are studied. We call it the generalized hierarchical product. In fact, the obtained graphs turn out to be subgraphs of the Cartesian product of the corresponding factors. Th...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics 2009-06, Vol.309 (12), p.3871-3881
Main Authors: Barrière, L., Dalfó, C., Fiol, M.A., Mitjana, M.
Format: Article
Language:English
Subjects:
Cartesian product
Coloring
Connectivity
Diameter
Graph
Hamiltonian cycle
Hierarchical product
Spectrum
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A generalization of both the hierarchical product and the Cartesian product of graphs is introduced and some of its properties are studied. We call it the generalized hierarchical product. In fact, the obtained graphs turn out to be subgraphs of the Cartesian product of the corresponding factors. Thus, some well-known properties of this product, such as a good connectivity, reduced mean distance, radius and diameter, simple routing algorithms and some optimal communication protocols, are inherited by the generalized hierarchical product. Besides some of these properties, in this paper we study the spectrum, the existence of Hamiltonian cycles, the chromatic number and index, and the connectivity of the generalized hierarchical product.
ISSN:0012-365X
1872-681X
DOI:10.1016/j.disc.2008.10.028