# On the representation number of a crown graph

@article{Glen2018OnTR, title={On the representation number of a crown graph}, author={Marc Glen and Sergey Kitaev and Artem V. Pyatkin}, journal={Discret. Appl. Math.}, year={2018}, volume={244}, pages={89-93} }

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 $xy$ is an edge in $E$. It is known that any word-representable graph $G$ is $k$-word-representable for some $k$, that is, there exists a word $w$ representing $G$ such that each letter occurs exactly $k$ times in $w$. The minimum such $k$ is called $G$'s representation number.
A crown graph $H_{n,n}$ is a graph obtained from the complete… Expand

#### 5 Citations

The k-cube is k-representable.

- Mathematics
- 2018

A graph is called $k$-representable if there exists a word $w$ over the nodes of the graph, each node occurring exactly $k$ times, such that there is an edge between two nodes $x,y$ if and only after… Expand

On the Representation Number of Bipartite Graphs

- Computer Science, Mathematics
- ArXiv
- 2021

A polynomial time relabeling algorithm is proposed to produce a word representing a given bipartite graph which is a concatenation of permutations of the graph’s vertices, which gives an upper bound for the representation number of bipartites. Expand

Polygon-circle and word-representable graphs

- Mathematics, Computer Science
- Electron. Notes Discret. Math.
- 2019

The relationship between the independently-studied polygon-circle graphs and word-representable graphs is described and it is shown that neither of these two classes is included in the other one by showing that the word- Representable Petersen graph and crown graphs are notpolygon- circle, while the non-word-Representable wheel graph W5 is polygon -circle. Expand

S ep 2 02 1 On the Representation Number of Bipartite Graphs

- 2021

A word-representable graph is a simple graph G which can be represented by a word w over the vertices of G such that any two vertices are adjacent in G if and only if they alternate in w. It is known… Expand

Symbolic Powers of Certain Cover Ideals of Graphs

- Mathematics
- 2019

In this paper, we compute the regularity and Hilbert series of symbolic powers of cover ideal of a graph G when G is either a crown graph or a complete multipartite graph. We also compute the… Expand

#### References

SHOWING 1-10 OF 15 REFERENCES

On Graphs with Representation Number 3

- Mathematics, Computer Science
- J. Autom. Lang. Comb.
- 2013

It is shown that any prism belongs to the class of graphs with representation number 3, denoted by $\mathcal{R}_3$, and that two particular operations of extending graphs preserve the property of being in this class. Expand

Word Problem of the Perkins Semigroup via Directed Acyclic Graphs

- Mathematics, Computer Science
- Order
- 2008

It is shown here that the computational complexity problem that has as instance {u,v} where u,v are words of finite length, and question “Is Alt(u) = Alt(v)?”, is co-NP-complete. Expand

Semi-transitive orientations and word-representable graphs

- Mathematics, Computer Science
- Discret. Appl. Math.
- 2016

An effective characterization of word-representable graphs in terms of orientations is given, showing that the recognition problem is in NP, and that word- Representable graphs include all 3-colorable graphs. Expand

On Representable Graphs

- Computer Science, Mathematics
- J. Autom. Lang. Comb.
- 2008

It is proved that a graph is representable if and only if it is k-representable for some k, and some wide classes of graphs are proven to be 2- and 3- representable. Expand

The Maximum Clique Problem

- Computer Science
- 2007

This paper considers the problem of finding the largest clique in a graph using the notation ES to represent the subset of edges which have both endpoints in clique S, and concludes that the induced graph GS = ( S, ES ) is complete. Expand

The Perkins Semigroup has Co-Np-Complete Term-Equivalence Problem

- Mathematics, Computer Science
- Int. J. Algebra Comput.
- 2005

It is proved here that $\mathbf{B^1_2}$, the six-element Perkins semigroup, has co-NP-complete term-equivalence problem, a result which leads to the completion of the classification of he term-Equivalence problems for monoid extensions of aperiodic Rees matrix semigroups. Expand

Coloring circle graphs

- Mathematics, Computer Science
- Electron. Notes Discret. Math.
- 2007

The bound χ ( G ) ⩽ ω ⋅ log n is presented which shows, that the circle graphs with small maximum clique and large chromatic number must have many vertices. Expand

Words and Graphs

- Computer Science
- Monographs in Theoretical Computer Science. An EATCS Series
- 2015

This is the first comprehensive introduction to the theory of word-representable graphs, a generalization of several classical classes of graphs, and a new topic in discrete mathematics. After… Expand

3-Coloring in Time O(1.3289^n)

- Computer Science, Mathematics
- J. Algorithms
- 2005

This work considers worst case time bounds for several NP-complete problems, based on a constraint satisfaction (CSP) formulation of these problems, and shows that n-variable (3, 2)-CSP instances can be solved in time O(1.3645n). Expand

ω-Perfect graphs

- Mathematics
- 1990

Abstractω-Perfect graph is defined and some classes of ω-perfect graphs are described, although the characterization of the complete class of ω-perfect graphs remains an open question. A bound on the… Expand