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

Kitaev, S., Salimov, P., Severs, C., & Ulfarsson, H. (2011). On the representability of line graphs. In G. Mauri, & A. Leporati (Eds.), Developments in Language Theory: 15th International Conference, DLT 2011, Milan, Italy, July 19-22, 2011. Proceedings (pp. 478-479). (Lecture Notes in Computer Science; Vol. 6795). https://doi.org/10.1007/978-3-642-22321-1_46
Kitaev, Sergey ; Salimov, Pavel ; Severs, Christopher ; Ulfarsson, Henning. / On the representability of line graphs. Developments in Language Theory: 15th International Conference, DLT 2011, Milan, Italy, July 19-22, 2011. Proceedings. editor / Giancarlo Mauri ; Alberto Leporati. 2011. pp. 478-479 (Lecture Notes in Computer Science).
@inproceedings{568aa8f852c54edebf343569bd1ca4c0,
title = "On the representability of line graphs",
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.",
keywords = "logics, line graphs, meanings of programs",
author = "Sergey Kitaev and Pavel Salimov and Christopher Severs and Henning Ulfarsson",
year = "2011",
doi = "10.1007/978-3-642-22321-1_46",
language = "English",
isbn = "978-3-642-22320-4",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "478--479",
editor = "Giancarlo Mauri and Alberto Leporati",
booktitle = "Developments in Language Theory",

}

Kitaev, S, Salimov, P, Severs, C & Ulfarsson, H 2011, On the representability of line graphs. in G Mauri & A Leporati (eds), Developments in Language Theory: 15th International Conference, DLT 2011, Milan, Italy, July 19-22, 2011. Proceedings. Lecture Notes in Computer Science, vol. 6795, pp. 478-479, 15th Conference on Developments in Language Theory, Milan, United Kingdom, 19/07/11. https://doi.org/10.1007/978-3-642-22321-1_46

On the representability of line graphs. / Kitaev, Sergey; Salimov, Pavel; Severs, Christopher; Ulfarsson, Henning.

Developments in Language Theory: 15th International Conference, DLT 2011, Milan, Italy, July 19-22, 2011. Proceedings. ed. / Giancarlo Mauri; Alberto Leporati. 2011. p. 478-479 (Lecture Notes in Computer Science; Vol. 6795).

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

TY - GEN

T1 - On the representability of line graphs

AU - Kitaev, Sergey

AU - Salimov, Pavel

AU - Severs, Christopher

AU - Ulfarsson, Henning

PY - 2011

Y1 - 2011

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

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

KW - logics

KW - line graphs

KW - meanings of programs

U2 - 10.1007/978-3-642-22321-1_46

DO - 10.1007/978-3-642-22321-1_46

M3 - Conference contribution book

SN - 978-3-642-22320-4

T3 - Lecture Notes in Computer Science

SP - 478

EP - 479

BT - Developments in Language Theory

A2 - Mauri, Giancarlo

A2 - Leporati, Alberto

ER -

Kitaev S, Salimov P, Severs C, Ulfarsson H. On the representability of line graphs. In Mauri G, Leporati A, editors, Developments in Language Theory: 15th International Conference, DLT 2011, Milan, Italy, July 19-22, 2011. Proceedings. 2011. p. 478-479. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-642-22321-1_46