# On graphs with representation number 3

Kitaev, Sergey
(2013)
*On graphs with representation number 3.*
Journal of Automata, Languages and Combinatorics, 18 (2).
pp. 97-112.

PDF (Kitaev-JALC-2015-On-graphs-with-representation-number-3)
Kitaev_JALC_2015_On_graphs_with_representation_number_3.pdf Accepted Author Manuscript Download (315kB) |

## Abstract

A graph $G=(V,E)$ is word-representable 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 word-representable if and only if it is $k$-word-representable for some $k$, that is, if there exists a word containing $k$ copies of each letter that represents the graph. Also, being $k$-word-representable implies being $(k+1)$-word-representable. The minimum $k$ such that a word-representable graph is $k$-word-representable, 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$-word-representable, and thus each ladder graph is a circle graph. Finally, we discuss $k$-word-representing comparability graphs via consideration of crown graphs, where we state some problems for further research.

Item type: | Article |
---|---|

ID code: | 51735 |

Notes: | Note that the paper was accepted on December 3rd 2014 but actually published in a 2013 volume; PURE couldn't accept this inconsistency |

Keywords: | word representable graphs, comparability graph, crown graph, circle graph, ladder graph, prism, representation number, Probabilities. Mathematical statistics, Discrete Mathematics and Combinatorics |

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: | 19 Sep 2018 01:26 |

Related URLs: | |

URI: | https://strathprints.strath.ac.uk/id/eprint/51735 |

Export data: |