On representable graphs

Sergey Kitaev; Artem Pyatkin

doi:10.25596/jalc-2008-045

On representable graphs

Sergey Kitaev, Artem Pyatkin

Research output: Contribution to journal › Article › peer-review

40 Downloads (Pure)

Abstract

A graph G = (V;E) is 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) 2 E for each x 6= y. If W is k-uniform (each letter of W occurs exactly k times in it) then G is called k-representable. We prove that a graph is representable if and only if it is k-representable for some k. Examples of non-representable graphs are found in this paper. Some wide classes of graphs are proven to be 2- and 3-representable. Several open problems are stated.

Original language	English
Pages (from-to)	45-54
Number of pages	10
Journal	Journal of Automata, Languages and Combinatorics
Volume	13
Issue number	1
DOIs	https://doi.org/10.25596/jalc-2008-045
Publication status	Published - 2008

Keywords

combinatorics on words
representation
(outer)planar graphs
prisms
Perkins semigroup
graph subdivisions

Access to Document

10.25596/jalc-2008-045

Kitaev-Pyatkin-JALC-2008-On-representable-graphsAccepted author manuscript, 244 KB

Cite this

@article{961ed69a95294515a40f64a0bb1f363d,

title = "On representable graphs",

abstract = "A graph G = (V;E) is 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) 2 E for each x 6= y. If W is k-uniform (each letter of W occurs exactly k times in it) then G is called k-representable. We prove that a graph is representable if and only if it is k-representable for some k. Examples of non-representable graphs are found in this paper. Some wide classes of graphs are proven to be 2- and 3-representable. Several open problems are stated.",

keywords = "combinatorics on words, representation, (outer)planar graphs, prisms, Perkins semigroup, graph subdivisions",

author = "Sergey Kitaev and Artem Pyatkin",

year = "2008",

doi = "10.25596/jalc-2008-045",

language = "English",

volume = "13",

pages = "45--54",

journal = "Journal of Automata, Languages and Combinatorics",

number = "1",

}

TY - JOUR

T1 - On representable graphs

AU - Kitaev, Sergey

AU - Pyatkin, Artem

PY - 2008

Y1 - 2008

N2 - A graph G = (V;E) is 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) 2 E for each x 6= y. If W is k-uniform (each letter of W occurs exactly k times in it) then G is called k-representable. We prove that a graph is representable if and only if it is k-representable for some k. Examples of non-representable graphs are found in this paper. Some wide classes of graphs are proven to be 2- and 3-representable. Several open problems are stated.

AB - A graph G = (V;E) is 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) 2 E for each x 6= y. If W is k-uniform (each letter of W occurs exactly k times in it) then G is called k-representable. We prove that a graph is representable if and only if it is k-representable for some k. Examples of non-representable graphs are found in this paper. Some wide classes of graphs are proven to be 2- and 3-representable. Several open problems are stated.

KW - combinatorics on words

KW - representation

KW - (outer)planar graphs

KW - prisms

KW - Perkins semigroup

KW - graph subdivisions

UR - https://personal.cis.strath.ac.uk/sergey.kitaev/index_files/Papers/repgr.pdf

U2 - 10.25596/jalc-2008-045

DO - 10.25596/jalc-2008-045

M3 - Article

VL - 13

SP - 45

EP - 54

JO - Journal of Automata, Languages and Combinatorics

JF - Journal of Automata, Languages and Combinatorics

IS - 1

ER -

On representable graphs

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this