On graphs with representation number 3
Kitaev, Sergey (2013) On graphs with representation number 3. Journal of Automata, Languages and Combinatorics, 18 (2). pp. 97112.
PDF.
Filename: Kitaev_JALC_2015_On_graphs_with_representation_number_3.pdf
Accepted Author Manuscript Download (315kB) 
Abstract
A 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 $(x,y)$ is an edge in $E$. A graph is wordrepresentable if and only if it is $k$wordrepresentable for some $k$, that is, if there exists a word containing $k$ copies of each letter that represents the graph. Also, being $k$wordrepresentable implies being $(k+1)$wordrepresentable. The minimum $k$ such that a wordrepresentable graph is $k$wordrepresentable, is called graph's representation number. Graphs with representation number 1 are complete graphs, while graphs with representation number 2 are circle graphs. The only fact known before this paper on the class of graphs with representation number 3, denoted by $\mathcal{R}_3$, is that the Petersen graph and triangular prism belong to this class. In this paper, we show that any prism belongs to $\mathcal{R}_3$, and that two particular operations of extending graphs preserve the property of being in $\mathcal{R}_3$. Further, we show that $\mathcal{R}_3$ is not included in a class of $c$colorable graphs for a constant $c$. To this end, we extend three known results related to operations on graphs. We also show that ladder graphs used in the study of prisms are $2$wordrepresentable, and thus each ladder graph is a circle graph. Finally, we discuss $k$wordrepresenting comparability graphs via consideration of crown graphs, where we state some problems for further research.


Item type: Article ID code: 51735 Dates: DateEvent2013Published3 December 2013AcceptedNotes: Note that the paper was accepted on December 3rd 2014 but actually published in a 2013 volume; PURE couldn't accept this inconsistency Subjects: Science > Mathematics > Probabilities. Mathematical statistics Department: Faculty of Science > Computer and Information Sciences Depositing user: Pure Administrator Date deposited: 18 Feb 2015 10:06 Last modified: 06 Jun 2024 01:16 Related URLs: URI: https://strathprints.strath.ac.uk/id/eprint/51735