Graph parameters, implicit representations and factorial properties

Alecu, B, Alekseev, VE, Atminas, A, Lozin, V and Zamaraev, V ORCID: 0000-0001-5755-4141
(2023) Graph parameters, implicit representations and factorial properties. DISCRETE MATHEMATICS, 346 (10). p. 113573.

[img] PDF
GIF-revision-2.pdf - Author Accepted Manuscript

Download (350kB) | Preview


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.

Item Type: Article
Uncontrolled Keywords: Graph parameter, Implicit representation, Hereditary class, Factorial property, Combinatorial Algorithms, IWOCA 2022
Divisions: Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User: Symplectic Admin
Date Deposited: 14 Jul 2023 09:16
Last Modified: 23 Aug 2023 22:52
DOI: 10.1016/j.disc.2023.113573
Related URLs: