Word-representability of line graphs

Sergey Kitaev, Pavel Salimov, Christopher Severs, Henning Ulfarsson

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) is in E for each x not equal to y . The motivation to study representable graphs came from algebra, but this subject is interesting from graph theoretical, computer science, and combinatorics on words points of view. In this paper, we prove that for n greater than 3, the line graph of an n-wheel is non-representable. This not only provides a new construction of non-repre- sentable graphs, but also answers an open question on representability of the line graph of the 5-wheel, the minimal non-representable graph. Moreover, we show that for n greater than 4, the line graph of the complete graph is also non-representable. We then use these facts to prove that given a graph G which is not a cycle, a path or a claw graph, the graph obtained by taking the line graph of G k-times is guaranteed to be non-representable for k greater than 3.
LanguageEnglish
Pages96-101
Number of pages6
JournalOpen Journal of Discrete Mathematics
Volume1
Issue number2
Publication statusPublished - Jul 2011

Fingerprint

Representability
Line Graph
Graph in graph theory
Wheel
Combinatorics on Words
Claw
Complete Graph
Alternate
Computer Science
If and only if
Cycle
Algebra
Path

Keywords

  • line graph
  • representability by words
  • wheel
  • complete graph

Cite this

Kitaev, S., Salimov, P., Severs, C., & Ulfarsson, H. (2011). Word-representability of line graphs. Open Journal of Discrete Mathematics, 1(2), 96-101.
Kitaev, Sergey ; Salimov, Pavel ; Severs, Christopher ; Ulfarsson, Henning. / Word-representability of line graphs. In: Open Journal of Discrete Mathematics. 2011 ; Vol. 1, No. 2. pp. 96-101.
@article{f31b7e99783544a1b8021aa95d92c948,
title = "Word-representability of line 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) is in E for each x not equal to y . The motivation to study representable graphs came from algebra, but this subject is interesting from graph theoretical, computer science, and combinatorics on words points of view. In this paper, we prove that for n greater than 3, the line graph of an n-wheel is non-representable. This not only provides a new construction of non-repre- sentable graphs, but also answers an open question on representability of the line graph of the 5-wheel, the minimal non-representable graph. Moreover, we show that for n greater than 4, the line graph of the complete graph is also non-representable. We then use these facts to prove that given a graph G which is not a cycle, a path or a claw graph, the graph obtained by taking the line graph of G k-times is guaranteed to be non-representable for k greater than 3.",
keywords = "line graph, representability by words, wheel, complete graph",
author = "Sergey Kitaev and Pavel Salimov and Christopher Severs and Henning Ulfarsson",
year = "2011",
month = "7",
language = "English",
volume = "1",
pages = "96--101",
journal = "Open Journal of Discrete Mathematics",
issn = "2161-7635",
number = "2",

}

Kitaev, S, Salimov, P, Severs, C & Ulfarsson, H 2011, 'Word-representability of line graphs' Open Journal of Discrete Mathematics, vol. 1, no. 2, pp. 96-101.

Word-representability of line graphs. / Kitaev, Sergey; Salimov, Pavel; Severs, Christopher; Ulfarsson, Henning.

In: Open Journal of Discrete Mathematics, Vol. 1, No. 2, 07.2011, p. 96-101.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Word-representability of line graphs

AU - Kitaev, Sergey

AU - Salimov, Pavel

AU - Severs, Christopher

AU - Ulfarsson, Henning

PY - 2011/7

Y1 - 2011/7

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) is in E for each x not equal to y . The motivation to study representable graphs came from algebra, but this subject is interesting from graph theoretical, computer science, and combinatorics on words points of view. In this paper, we prove that for n greater than 3, the line graph of an n-wheel is non-representable. This not only provides a new construction of non-repre- sentable graphs, but also answers an open question on representability of the line graph of the 5-wheel, the minimal non-representable graph. Moreover, we show that for n greater than 4, the line graph of the complete graph is also non-representable. We then use these facts to prove that given a graph G which is not a cycle, a path or a claw graph, the graph obtained by taking the line graph of G k-times is guaranteed to be non-representable for k greater than 3.

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) is in E for each x not equal to y . The motivation to study representable graphs came from algebra, but this subject is interesting from graph theoretical, computer science, and combinatorics on words points of view. In this paper, we prove that for n greater than 3, the line graph of an n-wheel is non-representable. This not only provides a new construction of non-repre- sentable graphs, but also answers an open question on representability of the line graph of the 5-wheel, the minimal non-representable graph. Moreover, we show that for n greater than 4, the line graph of the complete graph is also non-representable. We then use these facts to prove that given a graph G which is not a cycle, a path or a claw graph, the graph obtained by taking the line graph of G k-times is guaranteed to be non-representable for k greater than 3.

KW - line graph

KW - representability by words

KW - wheel

KW - complete graph

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

UR - http://www.scirp.org/journal/PaperInformation.aspx?PaperID=5808#.VEE5_KAtTTo

M3 - Article

VL - 1

SP - 96

EP - 101

JO - Open Journal of Discrete Mathematics

T2 - Open Journal of Discrete Mathematics

JF - Open Journal of Discrete Mathematics

SN - 2161-7635

IS - 2

ER -

Kitaev S, Salimov P, Severs C, Ulfarsson H. Word-representability of line graphs. Open Journal of Discrete Mathematics. 2011 Jul;1(2):96-101.