INDUCTIVE CLASSES OF GRAPHS
Definitions and Bibliography

In the paper an overview and bibliography on inductive definitions of classes of graphs is given.
Math. Subj. Class (1985): 05 C 10
Dear Colleagues,

In december 1987, during the XXX semester in Banach Center in Warsaw, I promissed to prepare, on the basis of my lectures, an overview on inductive definitions of classes of graphs. In November 1988 the first version with the extended bibliography from the paper [Bat86] was ready in LaTeX.

Since some participants of the Colloquium on Combinatorics (TU Braunschweig, 15-16th November 1996) expressed their interest for this overview I transfered it into HTML and put it on the Web. The data for last eight years are missing.

I would appreciate very much your comments and any additional information on the subject.

Vladimir Batagelj

Definitions

general
simple graphs
2-connected [Lov79]
3-connected [Tut61], [Tho80]
minimally 3-connected [Daw86]
4-connected [Fon78]
2-edge connected [Lov79]
planar connected [Mon70], [Lau81], [Bat86]
2-connected [Lau81]
3-connected [Tut61], [Lau81]
4-connected [Bar73], [Fon78]
triangulations plane all [Eb891], [Bru00], [StR34], [BoF67]
delta >= 4 [Bat84], [Ba87b]
delta >= 5 [Bat83]
even: deg mod 2 = 0 [Bat84], [Ba87b]
projective plane [Bar82]
torus [Lav87]
cubic graphs all [Ba81b]
connected [Joh66], [Ore67], [Ba81b]
2-connected [Ba81b]
3-connected [Ba81b]
cyclically 4-edge connected [Fon78]
chi' = 3 [FJR78], [FJR81]
chi' = chi = 3 [FJR78], [FJR81]
bipartite [Bat94]
bipartite w.o. C4 [Ma887], [Bat94]
planar all [Ba81b]
connected [Ba81b]
connected bipartite [Ba81b]
3-connected all [ErM79]
bipartite [Bat84], [HMM85], [Ba87b]
w.o. C3 [Bat84], [Ba87b]
w.o. C3 and C4 [Bat83]
cyclically 4-connected [Kot68]
strongly cyclically 4-connected [Bar74]
cyclically 5-connected [Bar74], [But74]
strongly cyclically 5-connected [Bar77]
quadrangulations
of the plane 		all [Ba87a]
3-connected [Ba87a]
4-regular graphs connected [Toi74], [BJF83]
planar connected [Man79], [Leh81]
3-connected [Ba87a]
r-regular (multi)graphs [Ba87c]
Eulerian graphs all [Bat96]
simple [Bat96]
simple planar [Bat96]

Bibliography

  1. Abe N., Mizumoto M., Toyoda J., Tanaka K.: Web Grammars and several Graphs. J. of Computer and System Sciences, 7(1973), 37-65.
  2. Alekseev V.E.: Nasledstvennye klassy i kodirovanie grafov. Problemy kibernetiki, 39. Nauka, Moskva, 1982, 151-164.
  3. Barnette D.: Generating planar 4-connected graphs. Israel J. Math. 14(1973), 1-13.
  4. Barnette D.: On generating planar graphs. Discrete mathematics 7(1974), 199-208.
  5. Barnette D.: Generating the c*5-connected graphs. Israel J. Math. 28(1977), no. 1-2, 151-160.
  6. Barnette D.: Generating the Triangulations of the Projective Plane. Journal of Combinatorial Theory, Series B 33(1982), 222-230.
  7. Batagelj V.: Inductive classes of cubic graphs. Colloquia Mathematica Societatis Janos Bolyai, 37. Finite and infinite sets, Eger 1981, 89-101.
  8. Batagelj, V.: An inductive definition of the class of all triangulations with no vertex of degree smaller than 5. Proceedings of the Fourth Yugoslav Seminar on Graph Theory, Novi Sad 1983, 15-25.
  9. Batagelj V.: Inductive definition of two restricted classes of triangulations. Discrete mathematics 52(1984), 113-121.
  10. Batagelj V.: Inductive classes of graphs. Proceedings of the Sixth Yugoslav Seminar on Graph Theory, Dubrovnik, april 18-19, 1985. Novi Sad 1986, 43-56.
  11. Batagelj V.: An inductive definition of the class of 3-connected quadrangulations of the plane. Discrete Mathematics 78(1989),45-53.
  12. Batagelj V.: An improved inductive definition of two restricted classes of triangulations of the plane. Combinatorics and Graph Theory, Banach Center Publications, Vol. 25, 11-18, PWN - Polish Scientific Publishers, Warsaw 1989.
  13. Batagelj V.: Inductive classes of regular graphs. Manuscript. (Presented at the Second Catania Combinatorial Conference, Santa Tecla, Italy, 4-9 september 1989).
  14. Batagelj V.: Inductive classes of bipartite cubic graphs. Discrete Mathematics, 134(1994), 3-8.
    (presented at the First Malta Conference on Graphs and Combinatorics, 28. may - 2. june 1990).
  15. Batagelj V.: Inductive classes of Eulerian graphs. Manuscript. (Presented at the Colloquium on Combinatorics, TU Braunschweig, 15-16th November 1996).
  16. Bories F., Jolivet J.L., Fouquet J.L.: Construction of 4-regular graphs. Annals of Discrete Mathematics 17(1983), 99-118.
  17. Bowen R.: The generation of minimal triangle graphs. Math. Comput (1967), 248-250.
  18. Bowen R., Fisk S.: Generation of triangulations of the sphere. Math. Comput (1967), 250-252.
  19. Brückner M.: Vielecke und Vielfläche: Theorie und Geschichte. Teubner, Leipzig 1900.
  20. Butler J.W.: A generation procedure for the simple 3-polytopes with cyclically 5-connected graphs. Canad. J. Math. 26(1974)3, 686-708.
  21. Claus V., Ehrig H., Rozenberg G. Eds.: Graph-Grammars and Their Application to Computer Science and Biology. Proceedings 1978. Lecture Notes in Computer Science 73. Springer Verlag, Berlin, New York 1979.
  22. Celmins U.A., Fouquet J.L., Swart E.R.: Construction and characterization of snarks. Journal of Graph Theory, 1983.
  23. Colbourn C.J., Read R.C.: Orderly Algorithms for Generating Restricted Classes of Graphs. Journal of Graph Theory 3(1979), 187-195.
  24. Curry H.B.: Foundations of Mathematical Logic. McGraw-Hill, New York 1963.
  25. Dawes R.W.: Minimally 3-connected graphs. Journal of Combinatorial Theory, Series B, 40(1986), 159-168.
  26. Eberhard V.: Zur Morphologie der Polyeder. Teubner, Leipzig, 1891.
  27. Earl C.F. and March L.J.: Architectural applications of graph theory. in Wilson R.J. and Beineke L.W. (Eds.), Applications of Graph Theory. Academic press, London 1979.
  28. Faradzhev I.A.: The generating of three-connected graphs and the enumeration of non-separable nets. Algorithmic studies in combinatorics, Work Collect., Moskva 1978, 67-69.
  29. Faulkner G.B., Younger D.H.: The recursive generation of cyclically k-connected cubic planar maps. Proceedings of the Twenty-Fifth Summer Meeting of the Canadian Mathematical Congres (Lakehead Univ., Thunder Bay, Ont., 1971), 349-356.
  30. Fontet M.: Graphs 4-essentiels. C.R. Acad.Sc.Paris, 287(1978), S\'erie A, 289-290.
  31. Fouquet J.L.: Note sur la nonexistance d'un snark d'ordre 16. Discrete Mathematics, 38(1982), 163-171.
  32. Fouquet J.L., Jolivet J.L., Riviere M.: Construction de classes de graphes cubiques. Coll. Mathematiques Discretes, Codes et Hypergraphes (1978), Cahiers du Centre d'Etudes et de Recherche Operationnelle 20(1978)3-4, 373-403.
  33. Fouquet J.L., Jolivet J.L., Riviere M.: Graphes cubiques d'indice trois, graphes cubiques isochromatiques, graphes cubiques d'indice quatre. Journal of Combinatorial Theory, Series B 31(1981)3, 262-281.
  34. Fouquet J.L., Jolivet J.L., Riviere M.: Structure and constructions of multi-3-gons with application to a hamiltonian problem. (preprint)
  35. Fouquet J.L., Jolivet J.L.: Strong Edge-Coloring of Cubic Planar Graphs. Progress in graph theory. Academic Press Canada, 1984, 247-264.
  36. Goodey P.R.: Hamiltonian circuits in polytopes with even sided faces. Israel Journal of Mathematics, 22(1975), 52-56.
  37. Griggs J.R., Kleitman D.J., Shastri A.: Spanning Trees with Many Leaves in Cubic Graphs. Journal of Graph Theory, 13(1989)6, 669-695.
  38. Grünbaum B.: Convex Polytopes. Wiley, New York 1967.
  39. Harary F.: Graph Theory. Addison-Wesley, Reading, Mass., 1969.
  40. Hecht M.S., Ullman J.D.: Flow graph reducibility. SIAM J. Computing, 1(1972), 188-202.
  41. Hedetniemi S.: Characterizations and constructions of minimally 2-connected graphs and minimally strong digraphs. Proceedings, 2nd Lousiaana Conference on Combinatorics, Graph Theory and Computing, 1971, 257-282.
  42. Holton D.A., Manvel B., McKay B.D.: Hamiltonian Cycles in Cubic 3-Connected Bipartite Planar Graphs. Journal of Combinatorial Theory, Series B, 38(1985), 279-297.
  43. Isaacs R.: Infinite families of nontrivial trivalent graphs which are not Tait colourable. American Mathematical Monthly, 82(1975), 221-239.
  44. Jendrol S., Tka"c M.: On the simplicial 3-polytopes with only two types of edges. Discrete Mathematics 48(1984), 229-241.
  45. Johnson E.L.: A proof of the four-coloring of the edges of a regular three-degree graph. American Mathematical Monthly, 73(1966), 52-55.
  46. Kelmans A.K.: Graph expansion and reduction. Algebraic methods in graph theory, Vol. I, Conf. Szeged 1978, Colloq. Math. Soc. Janos Bolyai 25, 317-343 (1981).
  47. Kelmans A.K.: O 3-svjaznyh grafah bez su"s"cestvennyh 3-razrezov i treugol'nikov. DAN 1985, 531-535.
  48. Kotzig A.: Regularly connected trivalent graphs without non-trivial cuts of cardinality 3. Acta Fac. Rerum Natur. Univ. Comenian. Math. Publ. 21(1968), 1-14.
  49. Läuchli P.: Generating all planar 0-, 1-, 2-, 3-connected graphs. (H. Noltemeier ed.: Graphtheoretic Concepts in Computer Science). Lecture Notes in Computer Science 100, Springer, Berlin 1981.
  50. Lavren"cenko S.A.: Neprivodimye trianguljacii tora. Ukrainskij geometri"ceskij sbornik 30(1987), 52-62.
  51. Lawson C.: Transforming Triangulations. Discrete Mathematics 3(1972), 365-372.
  52. Lehel J.: Generating all 4-regular planar graphs from the graph of the octahedron. Journal of Graph Theory, 5(1981), 423-426.
  53. Lovasz L.: Combinatorial problems and exercises. Akademiai Kiado, Budapest 1979.
  54. Manca P.: Generating All Planar Graphs Regular of Degree Four. J. of Graph Theory 3(1979), 357-364.
  55. Martinetti V.: Sulle configurazioni piane m3. Annali di mat. pura ed applicata 15(1887), 1-26.
  56. Mohar B.: Search for minimal non-hamiltonian simple 3-polytopes. Proceedings of the Fourth Yugoslav Seminar on Graph Theory, Novi Sad, 1983, 191-208.
  57. Montanari U.G.: Separable Graphs, Planar Graphs and Web Grammars. Information and Control 16(1970), 243-267.
  58. Ore O.: The Four-Color Problem. Academic Press, New York 1967.
  59. Pavlidis T.: Linear and Context-Free Graph Grammars. JACM 19(1972)1, 11-22.
  60. Pfaltz J.L., Rosenfeld A.: Web Grammars. Proc. Joint. Intern. Conf. on Art. Intell., Washington 1969.
  61. Plummer M.D., Pulleyblank W.R.: On proximity to paths and cycles in 3-connected graphs. Ars Combinatoria, 14(1982), 169-185.
  62. Raoult J.C.: On graph rewritings. Theoretical Computer Science 32(1984), 1-24.
  63. Read R.C., Wormald N.C.: Number of Labeled 4-Regular Graphs. Journal of Graph Theory 4(1980), 203-212.
  64. Rosen B.K.: Deriving graphs from graphs by applying a production. Acta Informatica 4(1975), 337-357.
  65. Slater P.: A classification of 4-connected graphs. Journal of Combinatorial Theory, Series B, 17(1974), 281-298.
  66. Steinitz E., Rademacher H.: Vorlesongen uber die Theorie der Polyeder. Springer, Berlin 1934.
  67. Takamizawa K., Nishizeki T., Saito N.: Combinatorial problems on series-parallel graphs. Proceedings: Graph theory and algorithms, Sendai, 1980. Lecture Notes in Computer Science, 180. Springer, Berlin, 1981, 79-94.
  68. Taylor R.: Switchings constrained to 2-connectivity in simple graphs. SIAM J. Alg. Disc. Meth. 3(1982)1, 114-121.
  69. Thomassen C.: Planarity and Duality of Finite and Infinite Graphs. Journal of Combinatorial Theory, Series B, 29(1980), 244-271.
  70. Toida S.: Construction de quartic graphes. Journal of Combinatorial Theory, Series B, 16(1974), 124-133.
  71. Tutte W.T.: On Hamiltonian circuits. Journal of London Mathematical Society, 21(1946), 98-101.
  72. Tutte W.T.: A theorem on planar graphs. Transactions of American Mathematical Society, 82(1956), 99-116.
  73. Tutte W.T.: A theory of 3-connected graphs. Nederl. Akad. Wetensch. Proc. Ser. A 64 = Indag. Math. 23 (1961), 441-455.
  74. Tutte W.T.: A census of planar maps. Canadian Journal of Mathematics, 15(1963), 249-271.
  75. Wankmüller F.: Characterization of graph classes by forbidden structures and reductions. Proceedings: Graph-grammars and their applications to computer science, Haus Ohrbeck, 1982. Lecture Notes in Computer Science, 153. Springer, Berlin, 1983, 405-414.
  76. Whitney H.: Congruent Graphs and the Connectivity of Graphs. American Journal of Mathematics, 54(1932), 150-168.
  77. Whitney H.: Non-Separable and Planar Graphs. Transactions of American Mathematical Society, 34(1932), 339-362.
  78. Wormald N.C.: Enumeration of Cyclically 4-Connected Cubic Graphs. Journal of Graph Theory, 9(1985), 563-573.
  79. Zaks J.: 6-valent analogues of Eberhard's theorem. Israel J. Math. 18(1974), 19-29.
Vladimir Batagelj, Department of Mathematics, University of Ljubljana, Jadranska 19, 1000 Ljubljana, Slovenia
First version: November 21, 1985; First HTML version: November 21, 1996