zbMATH — the first resource for mathematics

The generalized hierarchical product of graphs. (English) Zbl 1210.05120
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.

05C76 Graph operations (line graphs, products, etc.)
05C15 Coloring of graphs and hypergraphs
05C40 Connectivity
Full Text: DOI
[1] Albert, R.; Barabási, A.-L., Statistical mechanics of complex networks, Rev. modern phys., 74, 47-97, (2002) · Zbl 1205.82086
[2] Barrière, L.; Comellas, F.; Dalfó, C.; Fiol, M.A., The hierarchical product of graphs, Discrete appl. math., 157, 36-48, (2009) · Zbl 1200.05196
[3] Barrière, L.; Comellas, F.; Dalfó, C.; Fiol, M.A., On the spectra of hypertrees, Linear algebra appl., 428, 7, 1499-1510, (2008) · Zbl 1134.05051
[4] Bermond, J.-C., Hamiltonian graphs, (), 127-167
[5] Biggs, N., Algebraic graph theory, (1974), Cambridge University Press Cambridge, second ed. 1993 · Zbl 0284.05101
[6] Chartrand, G.; Lesniak, L., Graphs & digraphs, (1996), Chapman and Hall London · Zbl 0890.05001
[7] Cormen, T.H.; Leiserson, C.E.; Rivest, R.L.; Stein, C., Introduction to algorithms, (1990), MIT Press Cambridge, MA, second ed. 2001 · Zbl 1158.68538
[8] Cvetkovic, D.M.; Doob, M.; Sachs, H., Spectra of graphs. theory and applications, (1995), Johann Ambrosius Barth Heildelberg · Zbl 0824.05046
[9] Godsil, C.D., Algebraic combinatorics, (1993), Chapman and Hall New York · Zbl 0814.05075
[10] Hedetniemi, S.M.; Hedetniemi, S.T.; Liestman, A., A survey of gossiping and broadcasting in communication networks, Networks, 18, 319-349, (1988) · Zbl 0649.90047
[11] Lancaster, P.; Tismenetsky, M., The theory of matrices, (1985), Academic Press San Diego · Zbl 0516.15018
[12] Mahmoodian, E.S., On edge-colorability of Cartesian products of graphs, Canad. math. bull., 24, 107-108, (1981) · Zbl 0473.05030
[13] Mowshowitz, A., The group of a graph whose adjacency matrix has all distinct eigenvalues, (), 109-110 · Zbl 0193.24504
[14] Newman, M.E.J., The structure and function of complex networks, SIAM rev., 45, 167-256, (2003) · Zbl 1029.68010
[15] Ravasz, E.; Barabási, A.-L., Hierarchical organization in complex networks, Phys. rev. E, 67, 026112, (2003)
[16] Sabidussi, G., Graphs with given group and given graph-theoretical properties, Canad. J. math., 9, 515-525, (1957) · Zbl 0079.39202
[17] Silvester, J.R., Determinants of block matrices, Maths gaz., 84, 460-467, (2000)
[18] Špacapan, S., Connectivity of Cartesian products of graphs, Appl. math. lett., 21, 682-685, (2007) · Zbl 1152.05340
[19] Vizing, V.G., On an estimate of the chromatic class of a \(p\)-graph, Diskret. analiz., 3, 25-30, (1964)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.