Graph Parameters, Implicit Representations and Factorial Properties

Bogdan Alecu; Vladimir E. Alekseev; Aistis Atminas; Vadim Lozin; Viktor Zamaraev

doi:10.1007/978-3-031-06678-8_5

Graph Parameters, Implicit Representations and Factorial Properties

Bogdan Alecu, Vladimir E. Alekseev, Aistis Atminas, Vadim Lozin^*, Viktor Zamaraev

^*Corresponding author for this work

Department of Pure Mathematics

Research output: Chapter in Book or Report/Conference proceeding › Conference Proceeding › peer-review

1 Citation (Scopus)

Abstract

A representation of an n-vertex graph G is implicit if it assigns to each vertex of G a binary code of length O(log n) so that the adjacency of two vertices is a function of their codes. A necessary condition for a hereditary class X of graphs to admit an implicit representation is that X has at most factorial speed of growth. This condition, however, is not sufficient, as was recently shown in [10]. Several sufficient conditions for the existence of implicit representations deal with boundedness of some parameters, such as degeneracy or clique-width. In the present paper, we analyse more graph parameters and prove a number of new results related to implicit representation and factorial properties.

Original language	English
Title of host publication	Combinatorial Algorithms - 33rd International Workshop, IWOCA 2022, Proceedings
Editors	Cristina Bazgan, Henning Fernau
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	60-72
Number of pages	13
ISBN (Print)	9783031066771
DOIs	https://doi.org/10.1007/978-3-031-06678-8_5
Publication status	Published - 2022
Event	33rd International Workshop on Combinatorial Algorithms, IWOCA 2022 - Trier, Germany Duration: 7 Jun 2022 → 9 Jun 2022

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	13270 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	33rd International Workshop on Combinatorial Algorithms, IWOCA 2022
Country/Territory	Germany
City	Trier
Period	7/06/22 → 9/06/22

Keywords

Factorial property
Graph parameter
Hereditary class
Implicit representation

Access to Document

10.1007/978-3-031-06678-8_5

Cite this

Alecu, B., Alekseev, V. E., Atminas, A., Lozin, V., & Zamaraev, V. (2022). Graph Parameters, Implicit Representations and Factorial Properties. In C. Bazgan, & H. Fernau (Eds.), Combinatorial Algorithms - 33rd International Workshop, IWOCA 2022, Proceedings (pp. 60-72). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13270 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-031-06678-8_5

Alecu, Bogdan ; Alekseev, Vladimir E. ; Atminas, Aistis et al. / Graph Parameters, Implicit Representations and Factorial Properties. Combinatorial Algorithms - 33rd International Workshop, IWOCA 2022, Proceedings. editor / Cristina Bazgan ; Henning Fernau. Springer Science and Business Media Deutschland GmbH, 2022. pp. 60-72 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{6a8362245383495db2d0188ede40c389,

title = "Graph Parameters, Implicit Representations and Factorial Properties",

abstract = "A representation of an n-vertex graph G is implicit if it assigns to each vertex of G a binary code of length O(log n) so that the adjacency of two vertices is a function of their codes. A necessary condition for a hereditary class X of graphs to admit an implicit representation is that X has at most factorial speed of growth. This condition, however, is not sufficient, as was recently shown in [10]. Several sufficient conditions for the existence of implicit representations deal with boundedness of some parameters, such as degeneracy or clique-width. In the present paper, we analyse more graph parameters and prove a number of new results related to implicit representation and factorial properties.",

keywords = "Factorial property, Graph parameter, Hereditary class, Implicit representation",

author = "Bogdan Alecu and Alekseev, {Vladimir E.} and Aistis Atminas and Vadim Lozin and Viktor Zamaraev",

note = "Publisher Copyright: {\textcopyright} 2022, Springer Nature Switzerland AG.; 33rd International Workshop on Combinatorial Algorithms, IWOCA 2022 ; Conference date: 07-06-2022 Through 09-06-2022",

year = "2022",

doi = "10.1007/978-3-031-06678-8_5",

language = "English",

isbn = "9783031066771",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "60--72",

editor = "Cristina Bazgan and Henning Fernau",

booktitle = "Combinatorial Algorithms - 33rd International Workshop, IWOCA 2022, Proceedings",

}

Alecu, B, Alekseev, VE, Atminas, A, Lozin, V & Zamaraev, V 2022, Graph Parameters, Implicit Representations and Factorial Properties. in C Bazgan & H Fernau (eds), Combinatorial Algorithms - 33rd International Workshop, IWOCA 2022, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13270 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 60-72, 33rd International Workshop on Combinatorial Algorithms, IWOCA 2022, Trier, Germany, 7/06/22. https://doi.org/10.1007/978-3-031-06678-8_5

Graph Parameters, Implicit Representations and Factorial Properties. / Alecu, Bogdan; Alekseev, Vladimir E.; Atminas, Aistis et al.
Combinatorial Algorithms - 33rd International Workshop, IWOCA 2022, Proceedings. ed. / Cristina Bazgan; Henning Fernau. Springer Science and Business Media Deutschland GmbH, 2022. p. 60-72 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13270 LNCS).

Research output: Chapter in Book or Report/Conference proceeding › Conference Proceeding › peer-review

TY - GEN

T1 - Graph Parameters, Implicit Representations and Factorial Properties

AU - Alecu, Bogdan

AU - Alekseev, Vladimir E.

AU - Atminas, Aistis

AU - Lozin, Vadim

AU - Zamaraev, Viktor

PY - 2022

Y1 - 2022

N2 - A representation of an n-vertex graph G is implicit if it assigns to each vertex of G a binary code of length O(log n) so that the adjacency of two vertices is a function of their codes. A necessary condition for a hereditary class X of graphs to admit an implicit representation is that X has at most factorial speed of growth. This condition, however, is not sufficient, as was recently shown in [10]. Several sufficient conditions for the existence of implicit representations deal with boundedness of some parameters, such as degeneracy or clique-width. In the present paper, we analyse more graph parameters and prove a number of new results related to implicit representation and factorial properties.

AB - A representation of an n-vertex graph G is implicit if it assigns to each vertex of G a binary code of length O(log n) so that the adjacency of two vertices is a function of their codes. A necessary condition for a hereditary class X of graphs to admit an implicit representation is that X has at most factorial speed of growth. This condition, however, is not sufficient, as was recently shown in [10]. Several sufficient conditions for the existence of implicit representations deal with boundedness of some parameters, such as degeneracy or clique-width. In the present paper, we analyse more graph parameters and prove a number of new results related to implicit representation and factorial properties.

KW - Factorial property

KW - Graph parameter

KW - Hereditary class

KW - Implicit representation

UR - http://www.scopus.com/inward/record.url?scp=85131933643&partnerID=8YFLogxK

U2 - 10.1007/978-3-031-06678-8_5

DO - 10.1007/978-3-031-06678-8_5

M3 - Conference Proceeding

AN - SCOPUS:85131933643

SN - 9783031066771

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 60

EP - 72

BT - Combinatorial Algorithms - 33rd International Workshop, IWOCA 2022, Proceedings

A2 - Bazgan, Cristina

A2 - Fernau, Henning

PB - Springer Science and Business Media Deutschland GmbH

T2 - 33rd International Workshop on Combinatorial Algorithms, IWOCA 2022

Y2 - 7 June 2022 through 9 June 2022

ER -

Alecu B, Alekseev VE, Atminas A, Lozin V, Zamaraev V. Graph Parameters, Implicit Representations and Factorial Properties. In Bazgan C, Fernau H, editors, Combinatorial Algorithms - 33rd International Workshop, IWOCA 2022, Proceedings. Springer Science and Business Media Deutschland GmbH. 2022. p. 60-72. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-06678-8_5