On k11representable graphs
Cheon, GiSang and Kim, Jinha and Kim, Minki and Kitaev, Sergey and Pyatkin, Artem (2019) On k11representable graphs. Journal of Combinatorics, 10 (3). pp. 491513. ISSN 21563527

Text (CheonetalJC2018Onk11representablegraphs)
Cheon_etal_JC2018_On_k_11_representable_graphs.pdf Accepted Author Manuscript Download (317kB) Preview 
Abstract
Distinct 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 of the form xyxy... (of even or odd length) or a word of the form yxyx... (of even or odd length). A simple graph G=(V,E) is wordrepresentable if there exists a word w over the alphabet V such that letters x and y alternate in w if and only if xy is an edge in E. Thus, edges of G are defined by avoiding the consecutive pattern 11 in a word representing G, that is, by avoiding xx and yy. In 2017, Jeff Remmel introduced the notion of a k11representable graph for a nonnegative integer k, which generalizes the notion of a wordrepresentable graph. Under this representation, edges of G are defined by containing at most k occurrences of the consecutive pattern 11 in a word representing G. Thus, wordrepresentable graphs are precisely 011representable graphs. Our key result in this paper is showing that every graph is 211representable by a concatenation of permutations, which is rather surprising taking into account that concatenation of permutations has limited power in the case of 011representation. Also, we show that the class of wordrepresentable graphs, studied intensively in the literature, is contained strictly in the class of 111representable graphs. Another result that we prove is the fact that the class of interval graphs is precisely the class of 111representable graphs that can be represented by uniform words containing two copies of each letter. This result can be compared with the known fact that the class of circle graphs is precisely the class of 011representable graphs that can be represented by uniform words containing two copies of each letter.
Creators(s):  Cheon, GiSang, Kim, Jinha, Kim, Minki, Kitaev, Sergey ORCID: https://orcid.org/0000000333241647 and Pyatkin, Artem; 

Item type:  Article 
ID code:  65577 
Keywords:  k11representable graph, wordrepresentable graph, Electronic computers. Computer science, Computer Science(all) 
Subjects:  Science > Mathematics > Electronic computers. Computer science 
Department:  Faculty of Science > Computer and Information Sciences 
Depositing user:  Pure Administrator 
Date deposited:  01 Oct 2018 11:20 
Last modified:  08 Apr 2020 01:04 
URI:  https://strathprints.strath.ac.uk/id/eprint/65577 
Export data: 