Counting the Average Size of Markov Graphs


  • Sergiy Kozerenko


We calculate the average size (i.e. number of arcs) of Markov
graphs 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.


[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.





link situs slot gacor terbaru Situs toto togel 4D Toto Situs toto togel 4D Situs agen toto togel 4D Situs toto togel terpercaya bandar togel terpercaya toto togel 4D agen togel terpercaya togel4D situs togel terpercaya KASKUSTOTO slot deposit pulsa bandar togel 4d bandar togel 4d situs togel slot bandar togel resmi bandar togel 4d slot online gacor bandar slot pulsa situs togel 4d situs togel macau bandar togel macau situs togel hk judi slot online situs toto togel 4d situs toto togel keluaran toto togel slot togel 4d situs toto togel situs togel 4d toto togel resmi togel resmi 4d bandar togel 4d toto macau 4d bandar togel 4d slot deposit pulsa situs toto togel 4d situs macau terpercaya situs togel terpercaya keluaran togel macau situs toto togel situs slot online situs togel 4d situs togel toto toto togel 4d slot togel 4d situs togel terpercaya togel toto slot