Graph parameters, implicit representations and factorial properties

B. Alecu, V. E. Alekseev, A. Atminas, V. Lozin*, V. Zamaraev

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

6 Citations (Scopus)
Plum Print visual indicator of research metrics
  • Citations
    • Citation Indexes: 4
  • Captures
    • Readers: 1
see details

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.

Original languageEnglish
Article number113573
JournalDiscrete Mathematics
Volume346
Issue number10
DOIs
Publication statusPublished - Oct 2023

Keywords

  • Factorial property
  • Graph parameter
  • Hereditary class
  • Implicit representation

Fingerprint

Dive into the research topics of 'Graph parameters, implicit representations and factorial properties'. Together they form a unique fingerprint.

Cite this

Alecu, B., Alekseev, V. E., Atminas, A., Lozin, V., & Zamaraev, V. (2023). Graph parameters, implicit representations and factorial properties. Discrete Mathematics, 346(10), Article 113573. https://doi.org/10.1016/j.disc.2023.113573