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.
|
PDF
GIF-revision-2.pdf - Author Accepted Manuscript Download (350kB) | Preview |
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(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.
| 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: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3171677 |
Altmetric
Altmetric
