8 papers
On the representation number of chessboard graphs
Sergey Kitaev, Artem Pyatkin
The representation number of a graph is the smallest integer such that the graph can be represented by a word in which each vertex appears exactly times, and two distinct v…
Efficient k-mer Dataset Compression Using Eulerian Covers of de Bruijn Graphs and BWT
H. Z. Q. Chen, S. Kitaev, X. Lang +2
Transforming an input sequence into its constituent k-mers is a fundamental operation in computational genomics. To reduce storage costs associated with k-mer datasets, we introduc…
On the word-representability of - graphs
Herman Z. Q. Chen, Humaira Hameed, Sergey Kitaev
Word-representable graphs are a class of graphs that can be represented by words, where edges and non-edges are determined by the alternation of letters in those words. Several pap…
On the representation number of grid graphs and cylindric grid graphs
Nawaf Shafi Alshammari, Sergey Kitaev, Artem Pyatkin
The representation number of a graph is the minimum number of copies of each vertex required to represent the graph as a word, such that the letters corresponding to vertices a…
On 1-11-representability and multi-1-11-representability of graphs
Mohammed Alshammari, Sergey Kitaev, Chaoliang Tang +2
Jeff Remmel introduced the concept of a -11-representable graph in 2017. This concept was first explored by Cheon et al. in 2019, who considered it as a natural extension of wor…
A note on semi-transitivity of Mycielski graphs
Sergey Kitaev, Artem Pyatkin
An orientation of a graph is semi-transitive if it contains no directed cycles and has no shortcuts. An undirected graph is semi-transitive if it can be oriented in a semi-transiti…
New tools to study 1-11-representation of graphs
Mikhail Futorny, Sergey Kitaev, Artem Pyatkin
The notion of a -11-representable graph was introduced by Jeff Remmel in 2017 and studied by Cheon et al.\ in 2019 as a natural extension of the extensively studied notion of wo…
An embedding technique in the study of word-representabiliy of graphs
Sumin Huang, Sergey Kitaev, Artem Pyatkin
Word-representable graphs, which are the same as semi-transitively orientable graphs, generalize several fundamental classes of graphs. In this paper we propose a novel approach to…