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, (Proc. Nat. Acad. Sci. USA, 40 (1954)), 1004-1007 · Zbl 0055.42204
[4] Weinberg, L., Number of trees in a graph, (Proc. IRE, 46 (1958)), 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., The number of trees in a graph. II, 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), (Kibernetiku na sluz̆bu kommunizmu, Vol. 4 (1967), Gosènergoizdat: Gosènergoizdat Moscow) · 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, (Mat. Geometrie a teorie grafů (1970), Karlov Universitet: Karlov Universitet Praha)
[15] Moon, J. W., Enumerating labelled trees, (Harary, F., Graph Theory and Theoretical Physics (1967), Academic Press: Academic Press New York) · Zbl 0204.24502
[16] Kelmans, A. K., On the analysis and synthesis of random graphs (Russian), (Dissertation for Candidate’s Degree in Physical and Mathematical Sciences (1967), Institute of Control Sciences: Institute of Control Sciences Moscow) · 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), (Mat. Sb., 24 (1949), American Mathematical Society), 163-168, Translations, Number 79, 1952
[19] Hall, M., (Combinatorial Theory (1967), Blaisdell: Blaisdell Waltham, Mass) · Zbl 0196.02401
[20] Bellman, R., (Introduction to Matrix Analysis (1960), McGraw-Hill: McGraw-Hill New York) · Zbl 0124.01001
[21] Feller, W., (An Introduction to Probability Theory and Its Applications, Vol. I (1957), Wiley: Wiley New York) · Zbl 0077.12201
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.