Golden ratio in graph theory: a survey

Document Type : Review Article

Authors

Yazd University

Abstract

Much has been written about the golden ratio $\phi=\frac{1+\sqrt{5}}{2}$ and this strange number appears mysteriously in many mathematical calculations. In this article, we review the appearance of this number in the graph theory. More precisely, we review the relevance of this number in topics such as the number of spanning trees, topological indices, energy, chromatic roots, domination roots and the number of domatic partitions of graphs.

Graphical Abstract

Golden ratio in graph theory: a survey

Keywords

Main Subjects


[1] S. Akbari, S. Alikhani, Y. H. Peng, Characterization of graphs using domination polynomials, Eur. J. Combin. 31 (2010) 1714–1724.
[2] S. Alikhani, The domination polynomial of a graph at −1, Graphs Combin. 29 (2013) 1175–1181.
[3] S. Alikhani, D. Bakhshesh, N. Ghanbari, Counting the number of domatic partition of a graph, Available at https://arxiv.org/abs/2407.00103.
[4] S. Alikhani, M. A. Iranmanesh, Energy of graphs, matroids and Fibonacci numbers, Iranian J. Math. Sci. Inform. 5(2) (2010) 55–60.
[5] S. Alikhani, Y. H. Peng, Chromatic zeros and the golden ratio, Appl. Anal. Discrete Math. 3 (2009) 120–122.
[6] S. Alikhani, Y. H. Peng, Chromatic roots and generalized Fibonacci numbers, Appl. Anal. Discrete Math. 3(2) (2009) 330–335.
[7] S. Alikhani, R. Hasni, Algebraic integers as chromatic and domination roots, Int. J. Combin. 2012 (2012) 8, Article ID 780765.
[8] J. Arndt, Matters Computational: Ideas, Algorithms, Springer, 2011.
[9] R. B. Bapat, S. Pati, Energy of a graph is never an odd integer, Bull. Kerala Math. Assoc. 1 (2004) 129–132.
[10] H.-J. Bandelt, M. van de Vel, Embedding topological median algebras in products of dendrons, Proc. London Math. Soc. s3-58(3) (1989) 439–453.
[11] S. Barik, S. Pati, B.K. Sarma, The spectrum of the corona of two graphs, SIAM J. Discrete Math. 21(1) (2007) 47–56.
[12] A. E. Brouwer, The number of dominating sets of a finite graph is odd, preprint.
[13] E.J. Cockayne, S.T. Hedetniemi, Towards a theory of domination in graphs, Networks, 7 (1977) 247–261.
[14] M. V. Diudea, I. Gutman, L. Jantschi, Molecular Topology, Huntington, NY. 2001.
[15] F. M. Dong, K. M. Koh, K. L. Teo, Chromatic Polynomials and Chromaticity of Graphs, World Scientific Publishing Co. Pte. Ltd., 2005.
[16] ¨ O. Eˇ gecioˇglu, S. Klavˇ zar, M. Mollard, Fibonacci Cubes with Applications and Variations, World Scientific, 2023. [17] R. Frucht, R. Harary, On the corona of two graphs, Aequationes Mathematicae, 4 (1970) 322–325.
[18] I. Gutman, The energy of a graph, Ber. Math. Statist. Sekt. Forshungsz. Graz 103 (1987) 1–22.
[19] I. Gutman, O.E. Polansky, Mathematical Concepts in Organic Chemistry, Springer, Berlin, 1986.
[20] D.J. Harvey, G.F. Royle, Chromatic roots at 2 and the Beraha number B10, J. Graph Theory, 95(3) (2020) 445–456.
[21] T.W. Haynes, S.T. Hedetniemi, P.J. Slater, Fundamentals of Domination in Graphs, in: Chapman and Hall/CRC Pure and Applied Mathematics Series, Marcel Dekker, Inc. New York, 1998.
[22] T.W. Haynes, S.T. Hedetniemi, P.J. Slater, Domination in Graphs, Advanced Topics, Marcel Dekker, Inc., New York, 1998.
[23] H. Hosoya, Topological index, A newly proposed quantity characterizing the topological nature of structural isomers of saturated hydrocarbons, Bull.Chem.Soc.Jpn. 44(9) (1971) 2332–2339.
[24] Y. Huang, L. Shi, X. Xu, The Hosoya index and the Merrifield–Simmons index, J. Math. Chem. 56 (2018) 3136–3146. [25] W. Imrich, S. Klavˇ zar, H.M. Mulder, Median graphs and triangle-free graphs, SIAM J. Discrete Math. 12(1) (1999) 111–118.
[26] B. Jackson, A zero free interval for chromatic polynomials of graphs, Combin. Probab. Comput. 2 (1993) 325–336.
[27] D.J. Kleitman, B. Golden, Counting trees in a certain class of graphs, Amer. Math. Montly (1975) 40–44.
[28] F. Knox, F. Mohar, D.R. Wood, A golden ratio inequality for vertex degrees of graphs, Amer. Math. Monthly 126(8) (2019) 742–747.
[29] T. Koshy, Fibonacci and Lucas numbers with applications, A Willey-Interscience Publication, 2001.
[30] S. Pirzada, I. Gutman, Energy of graph is never the square root of an odd integer, Appl. Anal. Discr. Math. 2 (2008) 118–121.
[31] W.T. Tutte, On chromatic polynomials and the golden ratio, J. Combin. Theory, Ser B 9 (1970) 289296. 
[32] D. West, Introduction to Graph Theory, Prentice Hall, 2 edition, 2010.
[33] H. Wiener, Structural determination of paraffin boiling points, J. Am. Chem. Soc. 69 (1947) 17–20.
[34] B. Zelinka, Domination in the generalized Petersen graphs, Czechoslov. Math. J. 52(127) (2002) 11–16.
[35] B. Zelinka, Domatic number and degrees of vertices of a graph, Math. Slovaca 33 (1983) 145–147. [36] B. Zelinka, On domatic numbers of graphs, Math. Slovaca 31 (1981) 91–95.
Volume 9, Issue 2
June 2024
Pages 147-161
  • Receive Date: 12 April 2024
  • Revise Date: 29 April 2024
  • Accept Date: 15 May 2024
  • Publish Date: 01 June 2024