Graph parameters, implicit representations and factorial properties

B. Alecu; V. E. Alekseev; A. Atminas; V. Lozin; V. Zamaraev

doi:10.1016/j.disc.2023.113573

Graph parameters, implicit representations and factorial properties

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

^*Corresponding author for this work

Department of Pure Mathematics

Research output: Contribution to journal › Article › peer-review

6 Citations (Scopus)

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 language	English
Article number	113573
Journal	Discrete Mathematics
Volume	346
Issue number	10
DOIs	https://doi.org/10.1016/j.disc.2023.113573
Publication status	Published - Oct 2023

Keywords

Factorial property
Graph parameter
Hereditary class
Implicit representation

Access to Document

10.1016/j.disc.2023.113573

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

@article{69690f90ac1143058551fee61fab8c56,

title = "Graph parameters, implicit representations and factorial properties",

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.",

keywords = "Factorial property, Graph parameter, Hereditary class, Implicit representation",

author = "B. Alecu and Alekseev, {V. E.} and A. Atminas and V. Lozin and V. Zamaraev",

note = "Publisher Copyright: {\textcopyright} 2023 The Author(s)",

year = "2023",

month = oct,

doi = "10.1016/j.disc.2023.113573",

language = "English",

volume = "346",

journal = "Discrete Mathematics",

issn = "0012-365X",

number = "10",

}

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.

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(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.

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(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.

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 -

Graph parameters, implicit representations and factorial properties

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this