- Tytuł:
- Representing Split Graphs by Words
- Autorzy:
-
Chen, Herman Z.Q.
Kitaev, Sergey
Saito, Akira - Powiązania:
- https://bibliotekanauki.pl/articles/32222537.pdf
- Data publikacji:
- 2022-11-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
split graph
word-representability
semi-transitive orientation - Opis:
- There is a long line of research in the literature dedicated to word-representable graphs, which generalize several important classes of graphs. However, not much is known about word-representability of split graphs, another important class of graphs. In this paper, we show that threshold graphs, a subclass of split graphs, are word-representable. Further, we prove a number of general theorems on word-representable split graphs, and use them to characterize computationally such graphs with cliques of size 5 in terms of nine forbidden subgraphs, thus extending the known characterization for word-representable split graphs with cliques of size 4. Moreover, we use split graphs, and also provide an alternative solution, to show that gluing two word-representable graphs in any clique of size at least 2 may, or may not, result in a word-representable graph. The two surprisingly simple solutions provided by us answer a question that was open for about ten years.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2022, 42, 4; 1263-1280
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł