On the representability of line graphs

Sergey Kitaev, Pavel Salimov, Christopher Severs, Henning Ulfarsson

Research output: Chapter in Book/Report/Conference proceedingConference contribution book

7 Citations (Scopus)

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) ∈ E for each x ≠ y. Such a W is called a word-representant of G. Note that in this paper we use the term graph to mean a finite, simple graph, even though the definition of representable is applicable to more general graphs.
Original languageEnglish
Title of host publicationDevelopments in Language Theory
Subtitle of host publication15th International Conference, DLT 2011, Milan, Italy, July 19-22, 2011. Proceedings
EditorsGiancarlo Mauri, Alberto Leporati
Pages478-479
Number of pages2
DOIs
Publication statusPublished - 2011
Event15th Conference on Developments in Language Theory - University of Milano-Bicocca, Milan, United Kingdom
Duration: 19 Jul 201122 Jul 2011

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume6795
ISSN (Print)0302-9743

Conference

Conference15th Conference on Developments in Language Theory
CountryUnited Kingdom
CityMilan
Period19/07/1122/07/11

Keywords

  • logics
  • line graphs
  • meanings of programs

Cite this