Euler Graphs, Triangle-Free Graphs and Bipartite Graphs in Switching Classes | SpringerLink
Skip to main content
Springer Nature Link
Log in

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

  • Conference paper
  • First Online:
Graph Transformation (ICGT 2002)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 2505))

Included in the following conference series:

Abstract

In the context of graph transformations we look at the operation of switching, which can be viewed as an elegant 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 et al. 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.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. B. Aspvall, M.F. Plass, and R.E. Tarjan. A linear-time algorithm for testing the truth of certain quantified boolean formulas. Inf. Proc. Letters, 8(3):121–123, 1979.

    Article  MATH  MathSciNet  Google Scholar 

  2. P.J. Cameron. Cohomological aspects of two-graphs. Math. Z., 157:101–119, 1977.

    Article  MATH  MathSciNet  Google Scholar 

  3. D.G. Corneil and R.A. Mathon, editors. Geometry and Combinatorics: Selected Works of J.J. Seidel. Academic Press, Boston, 1991.

    Google Scholar 

  4. A. Ehrenfeucht, J. Hage, T. Harju, and G. Rozenberg. Complexity issues in switching of graphs. In H. Ehrig, G. Engels, H.-J. Kreowski, and G. Rozenberg, editors, Theory And Application Of Graph Transformations-TAGT’ 98, volume 1764 of Lecture Notes in Computer Science, pages 59–70, Berlin, 2000. Springer-Verlag.

    Google Scholar 

  5. A. Ehrenfeucht, T. Harju, and G. Rozenberg. The Theory of 2-Structures. World Scientific, 1999.

    Google Scholar 

  6. A. Ehrenfeucht and G. Rozenberg. Dynamic labeled 2-structures. Mathematical Structures in Computer Science, 4:433–455, 1994.

    Article  MATH  MathSciNet  Google Scholar 

  7. J.L. Gross and T.W. Tucker. Topological Graph Theory. Wiley, New York, 1987.

    MATH  Google Scholar 

  8. J. Hage. Structural Aspects Of Switching Classes. PhD thesis, LIACS, 2001. http://www.cs.uu.nl/people/jur/2s.html.

  9. J. Hage and T. Harju. A characterization of acyclic switching classes using forbidden subgraphs. Technical Report 5, Leiden University, Department of Computer Science, 2000. Submitted to Siam J. Disc. Math.

    Google Scholar 

  10. J. Kratochvýl, J. Nešetřil, and O. Zýka. On the computational complexity of Seidel’s switching, in: Combinatorics, Graphs and Complexity (M. Fiedler and J. Nešetřil eds.) Proceedings 4th Czechoslovak Symposium on Combinatorics, Prachatice 1990. Annals of Discrete Math., 51:161–166, 1992.

    Google Scholar 

  11. C.L. Mallows and N.J.A. Sloane. Two-graphs, switching classes and Euler graphs are equal in number. SIAM J. Appl. Math, 28:876–880, 1975.

    Article  MATH  MathSciNet  Google Scholar 

  12. J.J. Seidel. Graphs and two-graphs. In Proc. 5th Southeastern Conf. on Combinatorics, Graph Theory, amd Computing, Winnipeg, Canada, 1974. Utilitas Mathematica Publishing Inc.

    Google Scholar 

  13. J.J. Seidel. A survey of two-graphs. In Colloquio Internazionale sulle Teorie Combinatorie (Rome,1973), volume I, pages 481–511, Rome, 1976. Acc. Naz. Lincei. Reprinted in [3].

    MathSciNet  Google Scholar 

  14. J.J. Seidel and D.E. Taylor. Two-graphs, a second survey. In L. Lovasz and V.T. Sós, editors, Algebraic Methods in Graph Theory (Proc. Internat. Colloq., Szeged, 1978), volume II, pages 689–711, Amsterdam, 1981. North-Holland. Reprinted in [3].

    Google Scholar 

  15. T. Zaslavsky. Biased graphs. I. Bias, balance, and gains. J. Combin. Theory, Ser. B, 47:32–52, 1989.

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Inst. of Information and Computing Sci., Univ. Utrecht, P.O.Box 80.089, 3508, TB Utrecht, Netherlands

    Jurriaan Hage

  2. Dept. of Mathematics, University of Turku, FIN-20014, Turku, Finland

    Tero Harju

  3. Institut für Theoretische Informatik, ETH Zentrum, IFW B49.2, Haldeneggsteig 4, CH-8092, Zürich, Switzerland

    Emo Welzl

Authors
  1. Jurriaan Hage
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Tero Harju
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Emo Welzl
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Dipartimento di Informatica, Università di Pisa, Corso Italia 40, 56125, Pisa, Italy

    Andrea Corradini

  2. Computer Science Department, Technical University of Berlin, Franklinstraße 28/29, 10587, Berlin, Germany

    Hartmut Ehrig

  3. Computer Science Department, University of Bremen, Bibliothekstraße 1, 28359, Bremen, Germany

    Hans -Jörg Kreowski

  4. Leiden Institute of Advanced Computer Science, Leiden University, Niels Bohrweg 1, 2333, CA Leiden, The Netherlands

    Grzegorz Rozenberg

Rights and permissions

Reprints and permissions

Copyright information

© 2002 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Hage, J., Harju, T., Welzl, E. (2002). Euler Graphs, Triangle-Free Graphs and Bipartite Graphs in Switching Classes. In: Corradini, A., Ehrig, H., Kreowski, H.J., Rozenberg, G. (eds) Graph Transformation. ICGT 2002. Lecture Notes in Computer Science, vol 2505. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45832-8_13

Download citation

  • DOI: https://doi.org/10.1007/3-540-45832-8_13

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-44310-0

  • Online ISBN: 978-3-540-45832-6

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation