Abstract
| Language | English |
|---|---|
| Pages | 96-101 |
| Number of pages | 6 |
| Journal | Open Journal of Discrete Mathematics |
| Volume | 1 |
| Issue number | 2 |
| Publication status | Published - Jul 2011 |
Fingerprint
Keywords
- line graph
- representability by words
- wheel
- complete graph
Cite this
}
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 journal › Article
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 -