Word-Representability of Line Graphs
Affiliation(s)
Reykjavik University, School of Computer Science, Menntavegi 1, 101 Reykjavik, Iceland.
Reykjavik University, School of Computer Science, Menntavegi 1, 101 Reykjavik, Iceland.
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.
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.
Cite this paper
nullS. Kitaev, P. Salimov, C. Severs and H. Ulfarsson, "Word-Representability of Line Graphs," Open Journal of Discrete Mathematics, Vol. 1 No. 2, 2011, pp. 96-101. doi: 10.4236/ojdm.2011.12012.
nullS. Kitaev, P. Salimov, C. Severs and H. Ulfarsson, "Word-Representability of Line Graphs," Open Journal of Discrete Mathematics, Vol. 1 No. 2, 2011, pp. 96-101. doi: 10.4236/ojdm.2011.12012.
References
[1] S. Kitaev and A. Pyatkin, “On Representable Graphs,” Journal of Automata, Languages and Combinatorics, Vol. 13, No. 1, 2008, pp.45-54. [2] M. M. Halldórsson, S. Kitaev and A. Pyatkin, “Graphs Capturing Alternations in Words,” In Proceedings of the 14th international conference on Developments in language theory, London, August 17-20, 2010, pp. 436-437. [3] S. Kitaev and S. Seif, “Word Problem of the Perkins Semigroup via Directed Acyclic Graphs,” Order, Vol. 25, No. 3, 2008, pp. 177-194. doi:10.1007/s11083-008-9083-7 [4] R. Graham and N. Zang, “Enumerating Split-Pair Arrangements,” Journal of Combinatorial Theory, Series A, Vol. 115, No. 2, 2008, pp. 293-303. doi:10.1016/j.jcta.2007.06.003 [5] M. M. Halldorsson, S. Kitaev and A. Pyatkin, “On Representable Graphs, Semi-Transitive Orientations, and the Representation Numbers,” Submitted on 1 October 2008. http://arxiv.org/abs/0810.0310v1 [6] A. C. M. van Rooji and H. S. Wilf, “The Interchange Graph of a Finite Graph,” Acta Mathematica Academiae Scientiarum Hungaricae, Vol. 16, No. 3-4, 1965, pp.263- 269. doi:10.1007/BF01904834
[1] S. Kitaev and A. Pyatkin, “On Representable Graphs,” Journal of Automata, Languages and Combinatorics, Vol. 13, No. 1, 2008, pp.45-54. [2] M. M. Halldórsson, S. Kitaev and A. Pyatkin, “Graphs Capturing Alternations in Words,” In Proceedings of the 14th international conference on Developments in language theory, London, August 17-20, 2010, pp. 436-437. [3] S. Kitaev and S. Seif, “Word Problem of the Perkins Semigroup via Directed Acyclic Graphs,” Order, Vol. 25, No. 3, 2008, pp. 177-194. doi:10.1007/s11083-008-9083-7 [4] R. Graham and N. Zang, “Enumerating Split-Pair Arrangements,” Journal of Combinatorial Theory, Series A, Vol. 115, No. 2, 2008, pp. 293-303. doi:10.1016/j.jcta.2007.06.003 [5] M. M. Halldorsson, S. Kitaev and A. Pyatkin, “On Representable Graphs, Semi-Transitive Orientations, and the Representation Numbers,” Submitted on 1 October 2008. http://arxiv.org/abs/0810.0310v1 [6] A. C. M. van Rooji and H. S. Wilf, “The Interchange Graph of a Finite Graph,” Acta Mathematica Academiae Scientiarum Hungaricae, Vol. 16, No. 3-4, 1965, pp.263- 269. doi:10.1007/BF01904834