1. Graph parameters, implicit representations and factorial properties.
- Author
-
Alecu, B., Alekseev, V.E., Atminas, A., Lozin, V., and Zamaraev, V.
- Subjects
- *
COMPUTER storage devices , *BINARY codes , *FACTORIALS - Abstract
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 (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 [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. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF