On the Representability of Line Graphs

DOI10.1007/978-3-642-22321-1_46MaRDI QIDQ5199997zbMATH OpenOpenAlexFDO

Authors Sergey Kitaev, Christopher Severs, Henning Úlfarsson, Pavel Salimov

Publication date 29 July 2011

Published in Developments in Language Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1102.3980

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Graph theory (including graph drawing) in computer science (68R10)

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

Recommendations

• Word-representability of line graphs
• On representable graphs
• scientific article; zbMATH DE number 7011451
• On traceable line graphs
• Tulgeity of line graphs
• scientific article; zbMATH DE number 1161249
• Straight line representations of planar graphs
• On graphs supported by line sets
• scientific article; zbMATH DE number 3878977
• scientific article; zbMATH DE number 5943497

Cited in

(14)

• Traceability of line graphs
• Solving computational problems in the theory of word-representable graphs
• Word-representability of triangulations of grid-covered cylinder graphs
• Word-representability of face subdivisions of triangular grid graphs
• New results on word-representable graphs
• Word-Representable Graphs: a Survey
• scientific article; zbMATH DE number 7011451 (Why is no real title available?)
• scientific article; zbMATH DE number 1369943 (Why is no real title available?)
• Representing graphs via pattern avoiding words
• Existence of u-representation of graphs
• The \(k\)-dimensional cube is \(k\)-representable
• Word-representability of line graphs
• On representable graphs
• On word-representability of polyomino triangulations

This page was built for publication: On the Representability of Line Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5199997)