On representable graphs

Sergey Kitaev, Artem Pyatkin

Research output: Contribution to journalArticle

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 languageEnglish
Pages (from-to)45-54
Number of pages10
JournalJournal of Automata, Languages and Combinatorics
Volume13
Issue number1
Publication statusPublished - 2008

Fingerprint

Graph in graph theory
If and only if
Alternate
Open Problems
Class

Keywords

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

Cite this

Kitaev, Sergey ; Pyatkin, Artem. / On representable graphs. In: Journal of Automata, Languages and Combinatorics. 2008 ; Vol. 13, No. 1. pp. 45-54.
@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",
language = "English",
volume = "13",
pages = "45--54",
journal = "Journal of Automata, Languages and Combinatorics",
issn = "1430-189X",
number = "1",

}

On representable graphs. / Kitaev, Sergey; Pyatkin, Artem.

In: Journal of Automata, Languages and Combinatorics, Vol. 13, No. 1, 2008, p. 45-54.

Research output: Contribution to journalArticle

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

M3 - Article

VL - 13

SP - 45

EP - 54

JO - Journal of Automata, Languages and Combinatorics

JF - Journal of Automata, Languages and Combinatorics

SN - 1430-189X

IS - 1

ER -