TY - JOUR

T1 - Graph parameters, implicit representations and factorial properties

AU - Alecu, B.

AU - Alekseev, V. E.

AU - Atminas, A.

AU - Lozin, V.

AU - Zamaraev, V.

N1 - Publisher Copyright:
© 2023 The Author(s)

PY - 2023/10

Y1 - 2023/10

N2 - How to efficiently represent a graph in computer memory is a fundamental data structuring question. In the present paper, we address this question from a combinatorial point of view. A representation of an n-vertex graph G is called implicit if it assigns to each vertex of G a binary code of length O(logn) 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 [19]. 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 analyze more graph parameters and prove a number of new results related to implicit representation and factorial properties.

AB - How to efficiently represent a graph in computer memory is a fundamental data structuring question. In the present paper, we address this question from a combinatorial point of view. A representation of an n-vertex graph G is called implicit if it assigns to each vertex of G a binary code of length O(logn) 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 [19]. 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 analyze 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=85162762591&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2023.113573

DO - 10.1016/j.disc.2023.113573

M3 - Article

AN - SCOPUS:85162762591

SN - 0012-365X

VL - 346

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 10

M1 - 113573

ER -