On the hierarchical product of graphs

Document Type : Full Length Article

Authors

1 Montanuniversität Leoben, 8700 Leoben, Austria

2 AGH University of Krakow, 30-059 Krakow, Poland

Abstract

The hierarchical product of graphs is a variant of the Cartesian product. It is associative, not commutative, and finite connected graphs have unique first prime factors with respect to it. We present examples of infinite graphs with different first prime factors, and show that homogeneous trees of finite degree have unique prime factoriza-tions with respect to the hierarchical product. On the way, we pose two problems.

Graphical Abstract

On the hierarchical product of graphs

Keywords

Main Subjects


[1] S. E. Anderson, Y. Guo, A. Tenney, K. A. Wash, Prime factorization and domination in the hierar-
chical product of graphs, Discuss. Math. Graph Theory 37 (2017) 873–890, doi:10.7151/dmgt.1952.
[2] L. Barrière, F. Comellas, C. Dalfó, and M. A. Fiol, On the hierarchical product of
graphs and the generalized binomial tree, Linear Multilinear Algebra 57 (2009) 695–712,
doi:10.1080/03081080802305381.
[3] L. Barriére, F. Comellas, C. Dalfó, M. A. Fiol, The hierarchical product of graphs, Discrete Appl.
Math. 157 (2009) 36–48, doi:10.1016/j.dam.2008.04.018.
[4] L. Barriére, C. Dalfó, M. A. Fiol, M. Mitjana, The generalized hierarchical product of graphs, Dis-
crete Math. 309 (2009) 3871–3881, doi:10.1016/j.disc.2008.10.028.
[5] C. D. Godsil, B. D. McKay, A new graph product and its spectrum, Bull. Aust. Math. Soc. 18 (1978)
21–28, doi:10.1017/S0004972700007760.
[6] W. Imrich, R. Kalinowski, M. Pil´ sniak, Hierarchical product graphs and their prime factorization,
Art Discrete Appl. Math. accepted for publication 2024.
Volume 9, Issue 3
September 2024
Pages 163-171
  • Receive Date: 02 August 2024
  • Revise Date: 15 August 2024
  • Accept Date: 17 August 2024
  • Publish Date: 01 September 2024