A certain polynomial of a graph and graphs with an extremal number of trees. (English) Zbl 0277.05104


05C05 Trees
05C35 Extremal problems in graph theory
05C30 Enumeration in graph theory
Full Text: DOI


[1] Kirchhoff, G, Über die auflösung der gleichungen, auf welche man bei der untersuchung der linearen verteilung galvanischer ströme geführt wird, Ann. phys. chem., 72, 497-508, (1847)
[2] Lantieri, J, Méthode de détermination des arbres d’un réseau, Ann. Télécommun., 5, 204-208, (1950)
[3] Trent, H.M, A note on the enumeration and listing of all possible trees in a connected linear graph, (), 1004-1007 · Zbl 0055.42204
[4] Weinberg, L, Number of trees in a graph, (), 1954-1955
[5] Bedrosian, S.D, Formulas for the number of trees in a network, IRE trans. circuit thoery, CT-8, 363-364, (1961)
[6] O’Neil, P.V, The number of trees in a certain network, Notices amer. math. soc., 10, 569, (1963)
[7] Bedrosian, S.D, Generating formulas for the number of trees in a graph, J. franklin inst., 277, 313-326, (1964) · Zbl 0135.41904
[8] Kelmans, A.K; Kelmans, A.K, The number of trees in a graph. II, Avtomat. i telemeh., Avtomat. i telemeh., 27, 56-65, (1966), (Russian) · Zbl 0873.05065
[9] Kelmans, A.K, On properties of the characteristic polynomial of a graph (Russian), () · Zbl 0873.05065
[10] O’Neil, P.V; Slepian, P, The number of trees in a network, IEEE trans. circuit theory, CT-13, 271-281, (1966) · Zbl 0171.22501
[11] Oláh, G, A problem on the enumeration of certain trees (Russian), Studia sci. math. hungar., 3, 71-80, (1968) · Zbl 0184.49203
[12] O’Neil, P.V, Enumerating of spanning trees in a certain graph, IEEE trans. circuit theory, CT-17, 250, (1970)
[13] Bedrosian, S.D, Formulas for the number of trees in certain incomplete graphs, J. franklin inst., 289, 67-69, (1970) · Zbl 0297.05125
[14] Rohlickova, I, Poznámka a poctu koster jednoho typu grafu, ()
[15] Moon, J.W, Enumerating labelled trees, () · Zbl 0204.24502
[16] Kelmans, A.K, On the analysis and synthesis of random graphs (Russian), () · Zbl 0613.05034
[17] Lomonosov, M.V; Polesskiĭ, V.P, The lower bound for networks reliability, Problemy peredači informacii, 8, No. 2, (1972), translated as · Zbl 0335.05124
[18] Zykov, A.A, Some properties of linear complexes (Russian), (), 163-168, Translations, Number 79, 1952
[19] Hall, M, ()
[20] Bellman, R, ()
[21] Feller, W, ()
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.