On the Representability of Line Graphs

Details On the Representability of Line Graphs On the Representability of Line Graphs

2011-02-19

arxiv.org/abs/1102.3980v1

Open J. Discrete Math. 1 (2011) 96-101

Mathematics

Combinatorics

10 pages, 5 figures

Scientific paper

10.4236/ojdm.2011.12012

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-representable 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.

Affiliated with

Also associated with

No associations

Rating

On the Representability of Line Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the Representability of Line Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Representability of Line Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-159380