Word-representability of split graphs generated by morphisms

DOI10.1016/J.DAM.2022.02.023MaRDI QIDQ2127634zbMATH OpenOpenAlexFDO

Authors Kittitat Iamthong

Publication date 20 April 2022

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://arxiv.org/abs/2104.14872

zbMATH Keywords

morphismssemi-transitive orientationword-representable graphs

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph representations (geometric and intersection representations, etc.) (05C62) Combinatorics on words (68R15)

Abstract: 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$, $xeqy$, alternate in $w$ if and only if $xyinE$. A split graph is a graph in which the vertices can be partitioned into a clique and an independent set. There is a long line of research on word-representable graphs in the literature, and recently, word-representability of split graphs has attracted interest. In this paper, we first give a characterization of word-representable split graphs in terms of permutations of columns of the adjacency matrices. Then, we focus on the study of word-representability of split graphs obtained by iterations of a morphism, the notion coming from combinatorics on words. We prove a number of general theorems and provide a complete classification in the case of morphisms defined by $2imes2$ matrices.

Recommendations

• Word-representability of split graphs
• Representing split graphs by words
• On representable graphs
• Word-Representable Graphs: a Survey
• A comprehensive introduction to the theory of word-representable graphs

Cites work

• A comprehensive introduction to the theory of word-representable graphs
• scientific article; zbMATH DE number 3811868 (Why is no real title available?)
• scientific article; zbMATH DE number 3632548 (Why is no real title available?)
• Representing split graphs by words
• Semi-transitive orientations and word-representable graphs
• Word-representability of split graphs
• Word-representability of Toeplitz graphs
• Words and graphs

Cited in

(9)

• Word-representability of split graphs
• Representing split graphs by words
• Semi-transitivity of directed split graphs generated by morphisms
• On semi-transitive orientability of split graphs
• Word-representability of graphs with respect to split recomposition
• New tools to study 1-11-representation of graphs
• On the word-representability of K_m-K_n graphs
• Characterization of word-representable split graphs with an independent set of fixed size
• Word-representable co-bipartite graphs: representation number, speed, and entropy

This page was built for publication: Word-representability of split graphs generated by morphisms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2127634)