Counting the Average Size of Markov Graphs
Abstract
We calculate the average size (i.e. number of arcs) of Markovgraphs for several classes of vertex maps on finite trees. These are include arbitrary maps, permutations, cyclic permutations and the so-called neighbourhood maps. In the latter case we obtain an explicit formula for the size of corresponding Markov graphs and then provide sharp bounds for it in terms of the underlying trees.
References
[1] B. Bollobas and P. Erdos, Graphs of extremal weights, Ars Combin., 50 (1998), 225–233.
[2] D. Bonchev and N. Trinajsti´c, Information theory, distance matrix, and molecular branching, J. Chem. Phys., 67 (1977), 4517-4533.
[3] I. Gutman, A formula for the Wiener number of trees and its extension to graphs containing cycles, Graph Theory Notes N. Y., 27 (1994), 9–15.
[4] C-W. Ho and C. Morris, A graph theoretic proof of Sharkovsky’s theorem on the periodic points of continuous functions, Pacific J. Math., 96 (1981), 361–370.
[5] S. Klavzar, A. Rajapakse and I. Gutman, The Szeged and the Wiener index of graphs, Appl. Math. Lett., 9 (1996), 45–49.
[6] S. Kozerenko, Markov graphs of one-dimensional dynamical systems and their discrete analogues, Rom. J. Math. Comput. Sci., 6 (2016), 16–24.
[7] S. Kozerenko, Discrete Markov graphs: loops, fixed points and maps preordering, J. Adv. Math. Stud., 9 (2016), 99–109.
[8] X. Li and J. Zheng, A unified approach to the extremal trees for different indices, MATCH Commun. Math. Comput. Chem., 54 (2005), 195-208.
[9] A. Mili´cevi´c and S. Nikoli´c, On variable Zagreb indices, Croat. Chem. Acta., 77 (2004), 97–101.
[10] B. Mohar and T. Pisanski, How to compute the Wiener index of a graph, J. Math. Chem., 2 (1988), 267-277.
[11] H. Narumi and H. Katayama, Simple topological index A newly devised index characterizing the topological nature of structural isomers of saturated hydrocarbons, Mem. Fac. Engin.
Hokk. Univ., 16 (1984), 209-214.
[12] V. A. Pavlenko, Periodic digraphs and their properties, Ukrainian Math. J., 40 (1988), 455–458.
[13] P. D. Straffin, Periodic points of continuous functions, Math. Mag., 51 (1978), 99–105.
[14] M. Tchuente, Parallel calculation of a linear mapping on a computer network, Linear Algebra Appl., 28 (1979), 223–247.
[15] M. Tchuente, Parallel realization of permutations over trees, Discrete Math., 39 (1982), 211–214.
[16] H. Wiener, Structural determination of paraffin boiling points, J. Am. Chem. Soc., 69 (1947), 17–20.
[2] D. Bonchev and N. Trinajsti´c, Information theory, distance matrix, and molecular branching, J. Chem. Phys., 67 (1977), 4517-4533.
[3] I. Gutman, A formula for the Wiener number of trees and its extension to graphs containing cycles, Graph Theory Notes N. Y., 27 (1994), 9–15.
[4] C-W. Ho and C. Morris, A graph theoretic proof of Sharkovsky’s theorem on the periodic points of continuous functions, Pacific J. Math., 96 (1981), 361–370.
[5] S. Klavzar, A. Rajapakse and I. Gutman, The Szeged and the Wiener index of graphs, Appl. Math. Lett., 9 (1996), 45–49.
[6] S. Kozerenko, Markov graphs of one-dimensional dynamical systems and their discrete analogues, Rom. J. Math. Comput. Sci., 6 (2016), 16–24.
[7] S. Kozerenko, Discrete Markov graphs: loops, fixed points and maps preordering, J. Adv. Math. Stud., 9 (2016), 99–109.
[8] X. Li and J. Zheng, A unified approach to the extremal trees for different indices, MATCH Commun. Math. Comput. Chem., 54 (2005), 195-208.
[9] A. Mili´cevi´c and S. Nikoli´c, On variable Zagreb indices, Croat. Chem. Acta., 77 (2004), 97–101.
[10] B. Mohar and T. Pisanski, How to compute the Wiener index of a graph, J. Math. Chem., 2 (1988), 267-277.
[11] H. Narumi and H. Katayama, Simple topological index A newly devised index characterizing the topological nature of structural isomers of saturated hydrocarbons, Mem. Fac. Engin.
Hokk. Univ., 16 (1984), 209-214.
[12] V. A. Pavlenko, Periodic digraphs and their properties, Ukrainian Math. J., 40 (1988), 455–458.
[13] P. D. Straffin, Periodic points of continuous functions, Math. Mag., 51 (1978), 99–105.
[14] M. Tchuente, Parallel calculation of a linear mapping on a computer network, Linear Algebra Appl., 28 (1979), 223–247.
[15] M. Tchuente, Parallel realization of permutations over trees, Discrete Math., 39 (1982), 211–214.
[16] H. Wiener, Structural determination of paraffin boiling points, J. Am. Chem. Soc., 69 (1947), 17–20.
Downloads
Published
2017-02-02
Issue
Section
Чланци