×

zbMATH — the first resource for mathematics

Cycles in digraphs. A survey. (English) Zbl 0458.05035

MSC:
05C20 Directed graphs (digraphs), tournaments
05-02 Research exposition (monographs, survey articles) pertaining to combinatorics
05C38 Paths and cycles
05C45 Eulerian and Hamiltonian graphs
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Problem 2 in: Theory of graphs and its applications, Proc. Coll. Smolenice, Czech. Acad. Sci. Publ. (1964), 157.
[2] Adám, Acta Cybernet. 3 pp 3– (1976)
[3] Alpern, J. Combinatorial Theory B 25 pp 62– (1978)
[4] Alspach, Canad. Math. Bull 10 pp 283– (1967) · Zbl 0148.43602 · doi:10.4153/CMB-1967-028-6
[5] Alspach, J. Combinatorial Theory B 17 pp 11– (1974)
[6] Long paths and cycles in oriented p-partite graphs. Preprint (1980).
[7] Baranyai, J. Combinatorial Theory 19 (1981)
[8] Behzad, J. Math. Soc. Japan 25 pp 1– (1973)
[9] Behzad, Fund. Math. 69 pp 227– (1970)
[10] and , Cycles in complete oriented bipartite graphs. Preprint (1980).
[11] Beineke, Canad. Math. Bull. 8 pp 491– (1965) · Zbl 0132.21303 · doi:10.4153/CMB-1965-035-x
[12] and , , Selected Topics in Graph Theory. Edited by and . Academic Press, New York (1979).
[13] Bellmore, Oper. Res. 16 pp 538– (1968)
[14] On the number of 5-cycles in a tounament. Proc. 6th Southeastern Conf on Combinatorics, Graph Theory and Computing. Boca Raton, Utilitas Math., Congressus Numerantium XIV (1975), 101–108.
[15] Cycles dans les graphes et G-configurations. Thesis, University of Orsay (1975).
[16] Bermond, Cahiers du CERO, Bruxelles 17 pp 125– (1975a)
[17] The circuit hypergraph of a tournament, Infinite and finite sets. Colloq. Math. Soc. János Bolyai 10. North Holland (1975b), 165–180.
[18] On Hamiltonian walks. Proc. 5th British Combinatorial Conf, Aberdeen, Congressus Numerantiun XV. Utilitas Math. Publ. (1976), 41–51.
[19] Hamiltonian decompositions of graphs, directed graphs, and hypergraphs. Advances in Graph Theory. Edited by B. Bollobás. Ann. Discrete Math. 3 (1978), 21–28.
[20] Hamiltonian Graphs, Selected Topics in Graph Theory. Edited by and . Academic, New York (1979), 127–167.
[21] Problem in: Proc. Coll. Franco-Canadien de Combinatoire, Montreal, North-Holland, New York (1980).
[22] Bermond, J. Combinatorial Theory B 21 pp 146– (1976)
[23] , , and , Chemins et circuits dans les graphes orientés. Proc. Coll. Franco-Canadien de Combinatoire, Montréal, North Holland, New York (1980). · Zbl 0453.05032
[24] , , and , Longest paths in digraphs. Preprint (1980a).
[25] Bermond, J. Graph Theory 4 pp 337– (1980b)
[26] Bermond, Ars Combinatoria 5 pp 293– (1978)
[27] Bermond, RAIRO Informatique Théorique 10 pp 83– (1976)
[28] and , Problem 3, Recent advances in graph theory, Proc. Coll. Prague. Academia Prague (1975), 541.
[29] Bermond, Math. Japonica 4 pp 423– (1979)
[30] and , Graph decompositions and G-designs. Proc. 5th British Combinatorial Conf., Aberdeen, Congressus Numerantium XV. Utilitas Math. Publ. (1976), 53–72.
[31] and , Cycle and circuit designs, odd case, Beiträge zur Graphentheorie und deres Anwendungen. Proc. Coll. Oberhof Illmenau (1978), 11–32.
[32] Bondy, J. Combinatorial Theory B 11 pp 80– (1971)
[33] Bondy, Discrete Math. 1 pp 121– (1971a)
[34] Bondy, Canad. Math. Bull. 15 pp 57– (1972) · doi:10.4153/CMB-1972-012-3
[35] Pancyclic graphs. Proc. 2nd Louisiana Conf. on Combinatorics, Graph Theory and Computing. Utilitas Math. Publ. (1972a) 167–172.
[36] Bondy, J. London Math. Soc. 14 pp 277– (1976)
[37] Hamilton cycles in graphs and digraphs. Proc. 9th Southeastern Conf. on Combinatorics, Graph Theory and Computing, Boca Raton, Congressus Numerantium XXI. Utilitas Math. Publ. (1978), 3–28.
[38] Bondy, J. Combinatorial Theory B 16 pp 97– (1974)
[39] Bondy, Discrete Math. 19 pp 195– (1977)
[40] and , On minimal digraphs with given girth. Proc. 8th Southeastern Conf. on Combinatorics, Graph Theory and Computing, Boca Raton, Utilitas Math. Publ., Congressus Numerantium XXI (1978), 181–187.
[41] Camion, C. R. Acad. Sci. Paris 249 pp 2151– (1959)
[42] Camion, Cahiers CERO, Bruxelles 15 pp 225– (1973)
[43] Chartrand, J. Combinatorial Theory B 10 pp 12– (1971)
[44] Chartrand, Siam J. Appl. Math. 16 pp 696– (1968)
[45] Chartrand, Fund. Math. 65 pp 223– (1969)
[46] The travelling salesman problem, a survey. Preprint (1980).
[47] Chvátal, J. Combinatorial Theory B 12 pp 163– (1972)
[48] Chvátal, Discrete Math. 2 pp 111– (1972)
[49] Chvátal, J. Combinatorial Theory B 24 pp 61– (1978)
[50] Corradi, Acta Math. Acad. Sci. Hungar. 14 pp 423– (1963)
[51] Dirac, Proc. London Math. Soc. 2 pp 69– (1952)
[52] Dirac, Math. Ann. 206 pp 139– (1973)
[53] Dirac, Math. Ann. 203 pp 65– (1973)
[54] Douglas, Proc. London Math. Soc. 21 pp 716– (1970)
[55] Egorycev, Kombin. Anal. 3 pp 5– (1974)
[56] Erdös, Israel J. Math. 1 pp 156– (1963)
[57] Erdös, Acta Math. Acad. Sci. Hung. 10 pp 337– (1959)
[58] Erdös, Canad. Math. Bull. 8 pp 269– (1965) · Zbl 0137.43301 · doi:10.4153/CMB-1965-017-1
[59] Erdös, Publ. Math. Debrecen 9 pp 3– (1962)
[60] Erdös, Canad. J. Math. 17 pp 347– (1965) · Zbl 0129.39904 · doi:10.4153/CJM-1965-035-8
[61] Erdös, J. Graph Theory 2 pp 137– (1978)
[62] Forcade, Discrete Math. 6 pp 115– (1973)
[63] Fortune, Theor. Comput. Sci. 10 pp 111– (1980)
[64] Problèmes hamiltoniens dans les puissances de graphes, Problèmes Combinatoires et Théorie des Graphes. Proc. Coll. Orsay. CNRS Publ. (1978), 145–147.
[65] and , Graphes hypohamiltoniens orientés, Problèmes Combinatoires et Théorie des Graphes. Proc. Coll. Orsay. CNRS Publ. City (1978), 149–151.
[66] Problem at the Int. Coll. on Algebraic Methods in Graph Theory, Szeged (1978).
[67] On directed paths and circuits, Theory of Graphs. Proc. Colloq. Tihany 1966, Academic Press, New York (1968), 115–118.
[68] Problem 6 in: Theory of Graphs, Proc. Colloq. Tihany 1966, Academic Press, New York (1968a), 362.
[69] Garey, J. Combinatorial Theory B 13 pp 266– (1972)
[70] Ghouila-Houri, C. R. Acad. Sci. Paris 25 pp 495– (1960)
[71] Ghouila-Houri, Ann. Scient. Ac. Norm. Sup. 81 pp 317– (1964)
[72] Goldberg, J. London Math. Soc. 3 pp 378– (1971)
[73] Goldberg, Pacific J. Math. 40 pp 89– (1972) · Zbl 0207.23003 · doi:10.2140/pjm.1972.40.89
[74] , and , On graphs without antidirected elementary cycles and related topics. Preprint (1979).
[75] Grötschel, J. Graph Theory 3 pp 221– (1979)
[76] and , Hypohamiltonian digraphs, Report 7891-OR, Universität Bonn (1978).
[77] , and , Hypotraceable digraphs. J. Graph Theory (1980).
[78] Exercise 16.26, in F. Harary, Graph Theory. Addison-Wesley, Reading, Mass. (1969), 211.
[79] Problem 31 in Combinatorial structures and their applications, Proc. Coll. Calgary. Gordon and Breach Science City (1969a), 504–505.
[80] Grünbaum, J. Combinatorial Theory 11 pp 249– (1971)
[81] Gyori, Preprint Math. Inst. Hungar. Acad. Sci. 26 (1978)
[82] Hakimi, J. Combinatorial Theory B 17 pp 22– (1974)
[83] Hamidoune, Discrete Math. 26 pp 227– (1979)
[84] Connectivity of transitive digraphs and an application to combinatorial group theory. Proc. Coll. France-Canad. de Combinatoire, Montreal, Annals of Discrete Math. (1980).
[85] A note on the girth of a digraph. Preprint (1980a).
[86] On the number of edge disjoint circuits in graphs. Preprint, Aarhus Universitet (1975).
[87] On F-Hamiltonian graphs. Preprint, University of Umeaa (1977).
[88] Problem in Problem Session of the 6th British Combinatorial Conf., London, July (1977a) (unpublished).
[89] Häggkvist, J. Combinatorial Theory B 20 pp 20– (1976)
[90] Harary, Amer. Math. Month. 73 pp 231– (1966)
[91] , and , Structural models, An Introduction to the Theory of Directed Graphs. Wiley, New York (1965). · Zbl 0139.41503
[92] and , Graphical Enumeration. Academic Press, New York (1973).
[93] Heydemann, Discrete Math. 31 pp 217– (1980)
[94] Thesis, Université Paris-Sud (1980a).
[95] Jackson, J. Combinatorial Theory B 29 pp 27– (1980)
[96] Decompositions of graphs into cycles. Preprint (1980a).
[97] Paths and cycles in oriented graphs. Proc. Coll. Franco-Canad. de Combinatoire, Montreal, Annals of Discrete Math. (1980b). · Zbl 0444.05053
[98] Jackson, J. Graph Theory 3 (1981)
[99] Cycles and paths in tournaments. Thesis, University of Aarhus (1972).
[100] Johnson, SIAM J. Comput. 4 pp 77– (1975)
[101] Hamiltonian pseudo cycles in graphs. Proc. 5th Southeastern Conf. on Combinatorics, Graph Theory and Computing, Congressus Numerantium X, Utilitas Math. (1974), 529–533.
[102] On subgraphs without cycles in a tournament, Comb. Theory and its Appl., Proc. Colloq. Balatonfüred 1969. North-Holland 2 (1970), 675–677.
[103] Kasteleyn, Physica 29 pp 1319– (1963)
[104] Kendall, Biometrika 33 pp 239– (1940)
[105] Koh, Bull. Malaysian Math. Soc. 7 pp 47– (1976)
[106] and , Limit distribution of the existence of Hamilton cycles in a random graph. Preprint (1976).
[107] Koršunov, Soviet Math. Dokl. 19 pp 760– (1976)
[108] Some combinatorial problems on complete directed graphs, Theory of graphs. Proc. International Symposium Rome 1966. Dunod, Paris, and Gordon and Breach, New York (1967), 197–202.
[109] Kosaraju, J. Graph Theory 1 pp 379– (1977)
[110] The decomposition of a directed graph into quadratic factors consisting of cycles, Acta F. R. N. Univ. Comment. Math. XXII (1969), 27–29. · Zbl 0198.57203
[111] Kotzig, Discrete Math. 12 pp 17– (1975)
[112] Las Vergnas, C. R. Acad. Sci. Paris 272 pp 1297– (1971)
[113] Las Vergnas, Cahiers du CERO, Bruxelles 15 pp 231– (1973)
[114] Las Vergnas, Cahiers du CERO, Bruxelles 17 pp 261– (1975)
[115] Problem in: Problem Session, Proc. 5th British Conf. Congressus Numerantium XV. Utilitas Math. Publ. (1976), 689.
[116] Counterexample for Häggkvist’s conjecture. Preprint (1980).
[117] Lempel, J. Combinatorial Theory B 11 pp 17– (1971)
[118] Lesniak-Foster, J. Graph Theory 1 pp 27– (1977) · Zbl 0394.05020
[119] Lewin, J. Combinatorial Theory B 18 pp 175– (1975)
[120] Problem 11 in: Combinatorial Structures and their Applications. Proc. Coll. Calgary. Gordon and Breach, New York (1970), 497.
[121] Lovász, J. Combinatorial Theory B 21 pp 96– (1976)
[122] Lucchesi, J. London Math. Soc. 17 pp 369– (1978)
[123] Spanning subgraphs of k-connected digraphs. Preprint. (1979).
[124] Mateti, SIAM J. Comput. 5 pp 90– (1976)
[125] Meyniel, J. Combinatorial Theory B 14 pp 137– (1973)
[126] Extension des théorèmes de Turán et de Brooks et notion de stabilité et de coloration dans les graphes orientés. Preprint (1980).
[127] Démonstration constructive du Théoreme de Meyniel: un algorithme en O(n4) pour la détermination d’un circuit hamiltonien. Preprint (1980).
[128] Moon, Canad. Math. Bull. 7 pp 519– (1964) · Zbl 0141.41101 · doi:10.4153/CMB-1964-048-2
[129] Moon, Publ. Math. Debrecen 13 pp 145– (1966)
[130] Topics on Tournaments. Holt, Rinehart, and Winston, New York (1968).
[131] Moon, Canad. Math. Bull. 5 pp 5– (1962) · Zbl 0105.33401 · doi:10.4153/CMB-1962-002-0
[132] Müller, J. Combinatorial Theory B 24 pp 223– (1978)
[133] Problem 47 in: Theory of Graphs, Proc. Colloq. Tihany 1966. Academic Press, New York (1968), 366.
[134] Hamilton circuits in graphs and digraphs, The many facets of graph theory. Springer Verlag Lecture Notes 110 (1969), 237–243.
[135] Valency sequences which force graphs to have Hamiltonian circuits: Interim Report. University of Waterloo (1970).
[136] Hamiltonian circuits, Studies in Graph Theory Part II. Studies in Mathematics 12, M. A. A., Washington 1975, 301–360.
[137] Ninćak, Comment. Math. Univ. Carolinae 14 pp 135– (1973)
[138] Ore, Amer. Math. Monthly 67 pp 55– (1960)
[139] Ore, Ann. Math. Pure Appl. 55 pp 315– (1961)
[140] Overbeck-Larisch, J. Combinatorial Theory B 21 pp 76– (1976)
[141] Overbeck-Larisch, J. Combinatorial Theory B 23 pp 168– (1977)
[142] Palesti, Studia Sci. Math. Hungar. 6 pp 67– (1971)
[143] Pierce, Networks 5 pp 129– (1975)
[144] Pósa, Publ. Math. Inst. Hungar. Acad. Sci. 7 pp 225– (1962)
[145] Pósa, Publ. Math. Inst. Hungar. Acad. Sci. 8 pp 355– (1963)
[146] Pósa, Discrete Math. 14 pp 359– (1976)
[147] Read, Networks 5 pp 237– (1975)
[148] Rédei, Acta Litt. Szeged 7 pp 39– (1934)
[149] I-cycles in tournaments having no k-cycles. Proc. 2nd Louisiana Conf. on Combinatorics, Graph Theory, and Computing, Congressus Numerantium III. Univ. of Manitoba (1971), 473–482.
[150] Rosenfeld, J. Combinatorial Theory B 16 pp 234– (1974)
[151] Roy, RFAIRO 1 pp 127– (1967)
[152] Sekanina, Publ. Fac. Sci. Univ. Brno 412 pp 137– (1960)
[153] The multiplicity of Hamiltonian circuits in a graph. Recent Advances in Graph Theory, Proc. Prague Symp., Akad Prague (1975), 447–480.
[154] Skupién, Bull. Acad. Sci. 22 pp 463– (1974)
[155] Sotteau, J. Combinatorial Theory B 29 (1980)
[156] Thesis, Université Paris-Sud (1980a).
[157] Szele, Publ. Math. Debrecen 13 pp 145– (1966)
[158] and , Finding the elementary cycles of a directed graph in O(n+m) per cycle. Univ. of Newcastle upon Tyne (1974).
[159] Thomassen, Math. Ann. 200 pp 195– (1973)
[160] Thomassen, Math. Ann. 201 pp 231– (1973a)
[161] Thomassen, J. Reine Angew. Math. 268/269 pp 271– (1974)
[162] Thomassen, Math. Sci. Humaines. 51 pp 43– (1975)
[163] Paths and cycles in graphs. Ph. D. Thesis, University of Waterloo (1976).
[164] Thomassen, Discrete Math. 19 pp 85– (1977)
[165] Hypohamiltonian graphs and digraphs. Theory and applications of graph. Springer Verlag Lecture Notes 642 (1978), 557–570.
[166] Long cycles in digraphs with constraints on degrees, Survey in Combinatorics. Proc. 7th British Combinatorial Conf., London Math. Soc. Lecture Notes 38, Cambridge University Press (1979), 211–228.
[167] Thomassen, J. Combinatorial Theory B 28 pp 142– (1980a)
[168] Thomassen, Discrete Math. 31 pp 315– (1980b)
[169] Edge-disjoint Hamiltonian paths and cycles in tournaments. Preprint, Aarhus Universitit (1980c). · Zbl 0437.05026
[170] Long cycles in digraphs. Proc. London Math. Soc. (1981). · Zbl 0454.05029
[171] Tillson, J. Combinatorial Theory B 29 pp 68– (1980)
[172] Tutte, Trans. Amer. Math. Soc. 82 pp 99– (1956)
[173] Ph. D. Thesis, Louisiana State University (1978).
[174] and , Über Kreise in Graphen. VEB Deutscher Verlag 1974. · Zbl 0288.05101
[175] Whitney, Amer. J. Math. 54 pp 150– (1932)
[176] Woodall, Proc. London Math. Soc. 24 pp 739– (1972)
[177] Woodall, Acta Math. Acad. Sci. Hungar. 28 pp 77– (1976)
[178] Wright, Proc. Amer. Math. Soc. 41 pp 384– (1973)
[179] Younger, Proc. Midwest Symp. on Circuit Theory 2 pp xvi2.1– (1973)
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.