×

zbMATH — the first resource for mathematics

The hierarchical product of graphs. (English) Zbl 1200.05196
Summary: A new operation on graphs is introduced and some of its properties are studied. We call it hierarchical product, because of the strong (connectedness) hierarchy of the vertices in the resulting graphs. In fact, the obtained graphs turn out to be subgraphs of the cartesian product of the corresponding factors. Some well-known properties of the cartesian product, such as reduced mean distance and diameter, simple routing algorithms and some optimal communication protocols are inherited by the hierarchical product. We also address the study of some algebraic properties of the hierarchical product of two or more graphs. In particular, the spectrum of the binary hypertree \(T_m\) (which is the hierarchical product of several copies of the complete graph on two vertices) is fully characterized; turning out to be an interesting example of graph with all its eigenvalues distinct. Finally, some natural generalizations of the hierarchic product are proposed.

MSC:
05C76 Graph operations (line graphs, products, etc.)
05C12 Distance in graphs
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C90 Applications of graph theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Biggs, N., Algebraic graph theory, (1974), Cambridge University Press Cambridge, Second edition, 1993 · Zbl 0284.05101
[2] Cvetković, D.; Doob, M.; Sachs, H., Spectra of graphs. theory and applications, (1980), Academic Press New York · Zbl 0458.05042
[3] M.A. Fiol, M. Mitjana, The local spectra of regular line graphs, Discrete Math. (submitted for publication) E-prints UPC, UPCommons, http://hdl.handle.net/2117/735
[4] Fraigniaud, P.; Lazard, E., Methods and problems of communication in usual networks, Discrete appl. math., 53, 79-133, (1994) · Zbl 0818.94029
[5] Godsil, C.D., Algebraic combinatorics, (1993), Chapman and Hall New York · Zbl 0814.05075
[6] Jung, S.; Kim, S.; Kahng, B., Geometric fractal growth model for scale-free networks, Phys. rev. E, 65, 056101, (2002)
[7] Nelsen, R.B., Proofs without words: exercises in visual thinking, (1997), Math. Assoc. Amer Washington, DC · Zbl 1160.00303
[8] Newman, M.E.J., The structure and function of complex networks, SIAM rev., 45, 167-256, (2003) · Zbl 1029.68010
[9] Noh, J.D., Exact scaling properties of a hierarchical network model, Phys. rev. E, 67, 045103, (2003)
[10] Ravasz, E.; Barabási, A.-L., Hierarchical organization in complex networks, Phys. rev. E, 67, 026112, (2003)
[11] Ravasz, E.; Somera, A.L.; Mongru, D.A.; Oltvai, Z.N.; Barabási, A.-L., Hierarchical organization of modularity in metabolic networks, Science, 297, 1551-1555, (2002)
[12] Saad, Y.; Schultz, M.H., Topological properties of hypercubes, IEEE trans. comput., 37, 867-872, (1988)
[13] Schwenk, A.J., Computing the characteristic polynomial of a graph, Lect. notes math., 406, 153-172, (1974)
[14] Silvester, J.R., Determinants of block matrices, Math. gazette, 84, 460-467, (2000)
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.