Article in volume
Authors:
Title:
Representing split graphs by words
PDFSource:
Discussiones Mathematicae Graph Theory 42(4) (2022) 1263-1280
Received: 2019-11-23 , Revised: 2020-06-18 , Accepted: 2020-06-18 , Available online: 2020-07-20 , https://doi.org/10.7151/dmgt.2344
Abstract:
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.
Keywords:
split graph, word-representability, semi-transitive orientation
References:
- V. Chvátal and P.L. Hammer, Aggregation of inequalities in integer programming, in: Ann. Discrete Math. 1 (1977), P.L. Hammer, E.L. Johnson, B.H. Korte and G.L. Nemhauser (Ed(s)), (Studies in Integer Programming (Proc. Worksh. Bonn 1975) 145–162.
https://doi.org/10.1016/S0167-5060(08)70731-3 - S. Foldes and P.L. Hammer, Split graphs, in: Proc. Eighth Southeastern Conference on Combinatorics, Graph Theory and Computing, Congr. Numer. XIX (1977), (Louisiana State Univ., Baton Rouge 1977) 311–315.
- M. Glen, Software.
http://personal.strath.ac.uk/sergey.kitaev/word-representable-graphs.html - M. Golumbic, Algorithmic Graph Theory and Perfect Graphs (Elsevier Inc., 1980).
https://doi.org/10.1016/B978-0-12-289260-8.50010-8 - M.M. Halldórsson, S. Kitaev and A. Pyatkin, Semi-transitive orientations and word-representable graphs, Discrete Appl. Math. 201 (2016) 164–171.
https://doi.org/10.1016/j.dam.2015.07.033 - S. Kitaev, A comprehensive introduction to the theory of word-representable graphs, in: Developments in Language Theory, DLT 2017, E. Charlier, J. Leroy and M. Rigo (Ed(s)), Lecture Notes in Comput. Sci. 10396 (2017) 36–67.
https://doi.org/10.1007/978-3-319-62809-7_2 - S. Kitaev, Y. Long, J. Ma and H. Wu, Word-representability of split graphs.
arXiv: 1709.09725 - S. Kitaev and V. Lozin, Words and Graphs (Springer, 2015).
https://doi.org/10.1007/978-3-319-25859-1 - N.V.R. Mahadev and U.N. Peled, Threshold Graphs and Related Topics (Elsevier, 1995).
Close