Euler Graphs, Triangle-Free Graphs and Bipartite Graphs in Switching Classes

• Autorzy: Hage J. , Harju T. , Welzl E.
• Języki publikacji: EN

Abstrakty

EN

In the context of graph transformations we look at the operation of switching, which can be viewed as a method for realizing global transformations of graphs through local transformations of the vertices. A switching class is then a set of graphs obtainable from a given start graph by applying the switching operation. Continuing the line of research in Ehrenfeucht, Hage, Harju and Rozenberg we consider the problem of detecting three kinds of graphs in switching classes. For all three we find algorithms running in time polynomial in the number of vertices in the graphs, although switching classes contain exponentially many graphs.

Słowa kluczowe

EN

seidel switching; graph algorithms; complexity; NP-completeness

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2003
• Tom: Vol. 58, nr 1
• Strony: 23--37
• Opis fizyczny: Bibliogr. 19 poz., rys.

Twórcy

autor

Hage J.

• Institute of Information and Computing Sciences, Utrecht University, P.O. Box 80.089, 3508 TB, Utrecht the Netherlands

autor

Harju T.

• Department of Mathematics, University of Turku, FIN-20014 Turku, Finland

autor

Welzl E.

• Institut für Theoretische Informatik, ETH Zürich, CH - 8092 Zürich, Switzerland

Bibliografia

• [1] Aspvall, B., Plass, M. F., Tarjan, R. E.: A linear-time algorithm for testing the truth of certain quantified boolean formulas, Inf. Proc. Letters, 8(3), 1979, 121-123.
• [2] Cameron, P. J.: Cohomological aspects of two-graphs, Math. Z., 157, 1977, 101-119.
• [3] Ehrenfeucht, A., Hage, J., Harju, T., Rozenberg, G.: Complexity Issues in Switching of Graphs, Theory And Application Of Graph Transformations - TAGT ’98 (H. Ehrig, G. Engels, H.-J. Kreowski, G. Rozenberg, Eds.), 1764, Springer Verlag, Berlin, 2000.
• [4] Ehrenfeucht, A., Harju, T., Rozenberg, G.: The Theory of 2-Structures, World Scientific, 1999.
• [5] Ehrenfeucht, A., Rozenberg, G.: Dynamic labeled 2-structures, Mathematical Structures in Computer Science, 4, 1994, 433-455.
• [6] Gross, J. L., Tucker, T. W.: Topological Graph Theory, Wiley, New York, 1987.
• [7] Hage, J.: Structural Aspects Of Switching Classes, Ph.D. Thesis, Leiden Institute of Advanced Computer Science, 2001, Http://www.cs.uu.nl/people/jur/2s.html.
• [8] Hage, J., Harju, T.: A characterization of acyclic switching classes using forbidden subgraphs, Technical Report 5, Leiden University, Department of Computer Science, 2000, To appear in SIAM J. Disc. Math.
• [9] Hage, J., Harju, T., Welzl, E.: Euler Graphs, Triangle-Free Graphs and Bipartite Graphs in Swithing Classes, Graph Transformation, First Int. Conf, ICGT 2002 (A. Corradini, H. Ehrig, H.-J. Kreowski, G. Rozenberg, Eds.), 2505, Springer Verlag, Berlin, 2002.
• [10] Harary, F.: Graph Theory, Addison Wesley, 1972.
• [11] Hayward, R. B.: Recognizing􀀀-structure: a switching approach, J. Combin. Theory, Ser. B, 66, 1996, 247-262.
• [12] Itai, A., Rodeh, M.: Finding a minimum circuit in a graph, SIAM J. of Comput., 7, 1978, 413 - 423.
• [13] Kratochvíl, J., Něsetřil, J., Zýka, O.: On the computational complexity of Seidel’s switching, in: Combinatorics, Graphs and Complexity (M. Fiedler and J. Něsetřil eds.) Proceedings 4th Czechoslovak Symposium on Combinatorics, Prachatice 1990, Annals of Discrete Math., 51, 1992, 161-166.
• [14] van Lint, J. H., Seidel, J. J.: Equilateral points in elliptic geometry, Proc. Kon. Nederl. Acad. Wetensch., Ser. A, 69, 1966, 335-348, Reprinted in [?].
• [15] Mallows, C. L., Sloane, N. J. A.: Two-graphs, switching classes and Euler graphs are equal in number, SIAM J. Appl. Math, 28, 1975, 876-880.
• [16] Seidel, J. J.: Graphs and two-graphs, Proc. 5th Southeastern Conf. on Combinatorics, Graph Theory, and Computing, Utilitas Mathematica Publishing Inc., Winnipeg, Canada, 1974.
• [17] Seidel, J. J.: A survey of two-graphs, Intern. Coll. Teorie Combinatorie (Roma,1973), I, Accad. Naz. Lincei, Rome, 1976, Reprinted in [?].
• [18] Seidel, J. J., Taylor, D. E.: Two-graphs, a second survey, Algebraic Methods in Graph Theory (Proc. Internat. Colloq., Szeged, 1978) (L. Lovasz, V. Sós, Eds.), II, North-Holland, Amsterdam, 1981, Reprinted in [?].
• [19] Zaslavsky, T.: Biased graphs. I. Bias, balance, and gains, J. Combin. Theory, Ser. B, 47, 1989, 32-52