# zbMATH — the first resource for mathematics

Coding and counting spanning trees in Kleitman-Golden graphs. (English. Russian original) Zbl 0766.05036
Cybernetics 27, No. 3, 311-319 (1991); translation from Kibernetika 1991, No. 3, 1-7 (1991).
A Kleitman-Golden graph of order $$n$$ arises from the $$n$$-cycle $$C_ n$$ by joining every pair of vertices at distance 2 with an edge. Answering a question of S. D. Bedrosian [J. Franklin Inst. 295, 175-177 (1973; Zbl 0298.05104)], D. J. Kleitman and B. Golden showed that the number of spanning trees of this graph is $$nf^ 2_ n$$, where $$(f_ n)_{n\geq 1}$$ is the Fibonacci sequence defined by the initial conditions $$f_ 1=f_ 2=1$$. The paper gives another proof of this fact, based on a direct coding of spanning trees in Kleitman-Golden graphs by words in a three letter alphabet.

##### MSC:
 05C30 Enumeration in graph theory 05C05 Trees 11B39 Fibonacci and Lucas numbers and polynomials and generalizations
Full Text:
##### References:
 [1] F. Harary, Graph Theory, Addison-Wesley, Reading, MA (1969). [2] S. Bedrosian, ?The Fibonacci numbers via trigonometric expressions,? J. Franklin Inst.,295, No. 2, 175?177 (1973). · Zbl 0298.05104 · doi:10.1016/0016-0032(73)90227-5 [3] D. J. Kleitman and B. Golden, ?Counting trees in a certain class of graphs,? Am. Math. Monthly,82, No. 1, 40?44 (1975). · Zbl 0297.05123 · doi:10.2307/2319131 [4] S. Chaiken and D. J. Kleitman, ?Matrix tree theorems,? J. Combin. Theory,A24, No. 3, 377?381 (1978). · Zbl 0376.05032 · doi:10.1016/0097-3165(78)90067-5 [5] S. Chaiken, ?A combinatorial proof of all minors matrix tree theorem,? SIAM J. Algebr. Discr. Methods,3, No. 3 319?329 (1982). · Zbl 0495.05018 · doi:10.1137/0603033 [6] R. Vohra, and L. Washington, ?Counting spanning trees in the graphs of Kleitman and Golden and a generalization,? J. Franklin Inst.,318, No. 5, 349?355 (1984). · Zbl 0569.05016 · doi:10.1016/0016-0032(84)90054-1 [7] G. Baron, H. Prodinger, R. F. Tichy, et al., ?The number of spanning trees in the square of a cycle,? Fibonacci Quarterly,23, No. 3, 258?264 (1985). · Zbl 0587.05040 [8] F. T. Boesch and H. Prodinger, ?Spanning tree formulas and Chebyshev polynomials,? Graphs and Combinatorics,2, No. 3, 191?200 (1986). · Zbl 0651.05028 · doi:10.1007/BF01788093 [9] A. I. Vol’pert, ?Elementary proof of the Jordan theorem,? Usp. Mat. Nauk,5, No. 5(39), 168?172 (1950). [10] A. F. Filippov, ?Elementary proof of the Jordan theorem,? Usp. Mat. Nauk,5, No. 5(39), 173?176 (1950) [11] G.-C. Rota, ?Baxter algebras and combinatorial identities, II,? Bull. Am. Math. Soc.,75, No. 2, 330?334 (1969). · Zbl 0319.05008 · doi:10.1090/S0002-9904-1969-12158-0 [12] N. G. de Bruijn, ?Polya’s theory of counting,? in: Applied Combinatorial Mathematics [Russian translation], Mir, Moscow (1968), pp. 61?106. [13] A. Hurwitz, Theory of Analytical and Elliptical Functions [Russian translation], GTTI, Leningrad-Moscow (1933). [14] V. A. Krechmar, Problems in Algebra [in Russian], Nauka, Moscow (1968). [15] G. Polya and G. Szego, Problems and Theorems in Analysis, Springer, Berlin (1972). [16] J. Riordan, An Introduction to Combinatorial Analysis Wiley, New York (1958). · Zbl 0078.00805 [17] V. L. Goncharov, ?Topics in combinatorics,? Izv. Akad. nauk SSSR,8, No. 1, 3?48 (1944). [18] L. M. Koganov, ?Coding and counting spanning trees in Kleitman-Golden graphs,? Proc. Seminar on Discrete Mathematics and Its Applications [in Russian], O. B. Lupanov (ed.), Izd. Mosk. Gos. Univ., Moscow (1989). · Zbl 0766.05036
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.