Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Computer Aided Synthesis: A Game-Theoretic Approach Kapitel lesen Erstes Kapitel lesen

2017 | OriginalPaper | Buchkapitel

A Comprehensive Introduction to the Theory of Word-Representable Graphs

verfasst von : Sergey Kitaev

Erschienen in: Developments in Language Theory

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Letters x and y alternate in a word w if after deleting in w all letters but the copies of x and y we either obtain a word \(xyxy\cdots \) (of even or odd length) or a word \(yxyx\cdots \) (of even or odd length). A graph \(G=(V,E)\) is word-representable if and only if there exists a word w over the alphabet V such that letters x and y alternate in w if and only if \(xy\in E\).
Word-representable graphs generalize several important classes of graphs such as circle graphs, 3-colorable graphs and comparability graphs. This paper offers a comprehensive introduction to the theory of word-represent-able graphs including the most recent developments in the area.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel Computer Aided Synthesis: A Game-Theoretic Approach
Nächstes Kapitel Binomial Coefficients, Valuations, and Words
Fußnoten
1
The patterns considered in this section are ordered, and their study comes from Algebraic Combinatorics. There are a few results on word-representable graphs and (unordered) patterns studied in Combinatorics on Words, namely on squares and cubes in words, that are not presented in this paper, but can be found in [17, Sect. 7.1.3]. One of the results says that for any word-representable graph, there exists a cube-free word representing it.
 
Literatur
1.
Akrobotu, P., Kitaev, S., Masárová, Z.: On word-representability of polyomino triangulations. Siberian Adv. Math. 25(1), 1–10 (2015)MathSciNetCrossRefMATH
2.
Chen, T.Z.Q., Kitaev, S., Sun, B.Y.: Word-representability of face subdivisions of triangular grid graphs. Graphs Comb. 32(5), 1749–1761 (2016)MathSciNetCrossRefMATH
3.
Chen, T.Z.Q., Kitaev, S., Sun, B.Y.: Word-representability of triangulations of grid-covered cylinder graphs. Discr. Appl. Math. 213(C), 60–70 (2016)MathSciNetCrossRefMATH
4.
5.
6.
7.
8.
Glen, M., Kitaev, S.: Word-representability of triangulations of rectangular polyomino with a single domino tile. J. Comb. Math. Comb. Comput. (to appear)
9.
Halldórsson, M.M., Kitaev, S., Pyatkin, A.: Graphs capturing alternations in words. In: Gao, Y., Lu, H., Seki, S., Yu, S. (eds.) DLT 2010. LNCS, vol. 6224, pp. 436–437. Springer, Heidelberg (2010). doi:10.​1007/​978-3-642-14455-4_​41 CrossRef
10.
11.
Halldórsson, M., Kitaev, S., Pyatkin, A.: Semi-transitive orientations and word-representable graphs. Discrete Appl. Math. 201, 164–171 (2016)MathSciNetCrossRefMATH
12.
Jones, M., Kitaev, S., Pyatkin, A., Remmel, J.: Representing graphs via pattern avoiding words. Electron. J. Comb. 22(2), 2.53 (2015). 20 ppMathSciNetMATH
13.
Kim, J., Kim, M.: Graph orientations on word-representable graphs (in preparation)
14.
15.
Kitaev, S.: On graphs with representation number 3. J. Autom. Lang. Comb. 18(2), 97–112 (2013)MathSciNetMATH
16.
Kitaev, S.: Existence of \(u\)-representation of graphs. J. Graph Theor. 85(3), 661–668 (2017)CrossRef
17.
18.
Kitaev, S., Pyatkin, A.: On representable graphs. J. Autom. Lang. Comb. 13(1), 45–54 (2008)MathSciNetMATH
19.
Kitaev, S., Salimov, P., Severs, C., Úlfarsson, H.: On the representability of line graphs. In: Mauri, G., Leporati, A. (eds.) DLT 2011. LNCS, vol. 6795, pp. 478–479. Springer, Heidelberg (2011). doi:10.​1007/​978-3-642-22321-1_​46 CrossRef
20.
21.
22.
23.
Metadaten
Titel
A Comprehensive Introduction to the Theory of Word-Representable Graphs
verfasst von
Sergey Kitaev
Copyright-Jahr
2017
Buch
Developments in Language Theory

Print ISBN: 978-3-319-62808-0

Electronic ISBN: 978-3-319-62809-7

Copyright-Jahr: 2017

DOI
https://doi.org/10.1007/978-3-319-62809-7_2