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.

[thumbnail of Kitaev-JALC-2015-On-graphs-with-representation-number-3] PDF. Filename: 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.

ORCID iDs

Kitaev, Sergey ORCID logoORCID: https://orcid.org/0000-0003-3324-1647;
CORE (COnnecting REpositories)