Counting Paths, Circuits, Chains, and Cycles in Graphs: a Unified Approach

Biondi, E. ; Divieti, L. ; Guardabassi, G.

Canadian journal of mathematics, Tome 22 (1970) no. 1, pp. 22-35

Résumé

The problem of counting partial subgraphs (or patterns, for short) in a given graph has been approached by several mathematicians from various points of view (see, e.g., [1; 3; 5; 13-15; 17-23; 26-29]; applications may also be found in [2; 8; 9; 16]). Specific algorithms have been presented and almost all of them are essentially based upon a careful analysis of the graph under consideration. In these cases, we say that a direct approach has been followed. Unfortunately, when large graphs are considered, all direct counting methods require rather cumbersome computations. For this reason, during the last few years many efforts have been made in finding suitable indirect counting methods. First, Biondi [5] faced the problem of counting cycles in non-oriented graphs by inspection of the complementary graph. More recently, a number of papers [1; 3; 21; 22; 28] have been concerned with counting trees in classes of non-oriented graphs having complementary graphs with special structural properties. However, to the best of our knowledge, no general indirect counting method is available in the literature.

Détail

DOI : 10.4153/CJM-1970-003-9

Bibliographie

[1] 1. Bedrosian, S. D., Formulas for the number of trees in a network, IRE Trans. Circuit Theory (Correspondence) 8 (1961), 363–364. Google Scholar

[2] 2. Bedrosian, S. D., Application of linear graphs to multi-level maser analysis•, J. Franklin Inst. 274 (1962), 278–283. Google Scholar

[3] 3. Bedrosian, S. D., Generating formulas for the number of trees in a graph, J. Franklin Inst. 277 (1964), 313–326. Google Scholar

[4] 4. Berge, C., The theory of graphs and its applications (Methuen, London, 1962). Google Scholar

[5] 5. Biondi, E., Numerazione delle maglie in una rete qualsiasi, 1st. Lombardo (Accad. Sci. Lett. Rend. A 91 (1957), 912–926. Google Scholar

[6] 6. Biondi, E., Divieti, L., and Guardabassi, G., A paths counting method, Relazione Interna LE 66-7, Istituto di Elettrotecnica ed Elettronica del Politecnico di Milano (Milano, 1966). Google Scholar

[7] 7. Divieti, L., Un metodo per la determinazione dei sottografi completi di un grafo assegnato, Relazione Interna LE 65-5 Istituto di Elettrotecnica ed Elettronica del Politecnico di Milano (Milano, 1965). Google Scholar

[8] 8. Epstein, V. L., On the application of graph theory to the description and analysis of information flows schemes in control systems, Avtomat. i Telemeh 26 (1965), 1403-1410; translated as Automat. Remote Control 26 (1965), 1378–1383. Google Scholar

[9] 9. Flament, C., Nombre de cycles complets dans un reseau de communication, Bull. Centre Etudes Rech. Psych. 3 (1959), 105–110. Google Scholar

[10] 10. Guardabassi, G., Counting patterns in graphs: a necessary planarity condition, Relazione Interna LE 66-6, Istituto di Elettrotecnica ed Elettronica del Politecnico di Milano (Milano, 1966). Google Scholar

[11] 11. Guardabassi, G., On the number of trees in a network (to appear). Google Scholar

[12] 12. Guardabassi, G., Counting constrained routes in complete networks: the H-function, unpublished note. Google Scholar

[13] 13. Harary, F. and Ross, I. C., The number of complete cycles in a communication network, J. Social Psych. 40 (1954), 329–332. Google Scholar

[14] 14. Katz, L., An application of matrix algebra to the study of human relations within organizations, Mimeographed notes, Institute of Statistics, University of North Carolina, 1950. Google Scholar

[15] 15. Kel'mans, A. K., The number of trees in a graph. I, Avtomat. i. Telemeh 26 (1965), 2194– 2204; translated as Automat. Remote Control 26 (1965), 2118-2129 (1966). Google Scholar

[16] 16. Kendall, M. G., Rank correlation methods (C. Griffin, London, 1948). Google Scholar

[17] 17. Kendall, M. G., Further contributions to the theory of paired comparisons, Biometrics 11 (1955), 43–62. Google Scholar

[18] 18. Luce, R. D. and Perry, A. D., A method of matrix analysis of group structure, Psychometrika 14 (1949), 95–116. Google Scholar

[19] 19. Lunelli, L., Numerazione delle maglie in una rete compléta, 1st. Lombardo Accad. Sci. Lett. Rend. A 91 (1957), 903–911. Google Scholar

[20] 20. Nakagawa, N., On evaluation of the graph trees and the driving point admittance, IRE Trans. Circuit Theory 5 (1958), 122–127. Google Scholar

[21] 21. O'Neil, P. V., The number of trees in a certain network, Amer. Math. Soc. Meeting, 604, Brooklyn, New York, 1963; Notices Amer. Math. Soc. 10 (1963), 569. Google Scholar

[22] 22. O'Neil, P. V. and Slepian, P., The number of trees in a network, IEEE Trans. Circuit Theory 15 (1966), 271–281. Google Scholar

[23] 23. O'Neil, P. V. and Slepian, P., An application of Feussner's method to tree counting, IEEE Trans. Circuit Theory (Correspondence) 13 (1966), 336–339. Google Scholar

[24] 24. Pototchi, A., A simple algorithm for determining the number of paths in a finite graph, Economic Computation and Economic Cybernetics Studies and Research 2 (1967), 81–85. Google Scholar

[25] 25. Riordan, J., An introduction to combinatorial analysis (Wiley, New York, 1958). Google Scholar

[26] 26. Ross, I. C. and Harary, F., On the determination of redundancies in sociometric chains, Psychometrika 17 (1952), 195–208. Google Scholar

[27] 27. Trent, H. M., A note on the enumeration and listing of all possible trees in a connected linear graph, Proc. Nat. Acad. Sci. 40 (1954), 1004–1007. Google Scholar

[28] 28. Weinberg, L., Number of trees in a graph, IRE Proc. (Correspondence) 46 (1958), 1954–1955. Google Scholar

[29] 29. Wilf, H. S., A mechanical counting method and combinatorial applications, J. Combinatorial Theory 4 (1968), 246–258. Google Scholar