The Library
Graph parameters, implicit representations and factorial properties
Tools
Tools
Tools
Alecu, B., Alekseev, V.E., Atminas, A., Lozin, Vadim V. and Zamaraev, V. (2023) Graph parameters, implicit representations and factorial properties. Discrete Mathematics, 346 (10). 113573. doi:10.1016/j.disc.2023.113573 ISSN 0012-365X.
|
PDF
1-s2.0-S0012365X23002595-main.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (504Kb) | Preview |
Official URL: http://dx.doi.org/10.1016/j.disc.2023.113573
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 0(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: | Journal Article | ||||||||
|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | ||||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||||||
| Library of Congress Subject Headings (LCSH): | Graph theory, Mathematical optimization, Combinatorial analysis , Factorials , Computer science -- Mathematics | ||||||||
| Journal or Publication Title: | Discrete Mathematics | ||||||||
| Publisher: | Elsevier | ||||||||
| ISSN: | 0012-365X | ||||||||
| Official Date: | October 2023 | ||||||||
| Dates: |
|
||||||||
| Volume: | 346 | ||||||||
| Number: | 10 | ||||||||
| Article Number: | 113573 | ||||||||
| DOI: | 10.1016/j.disc.2023.113573 | ||||||||
| Status: | Peer Reviewed | ||||||||
| Publication Status: | Published | ||||||||
| Access rights to Published version: | Open Access (Creative Commons) | ||||||||
| Date of first compliant deposit: | 3 July 2023 | ||||||||
| Date of first compliant Open Access: | 5 July 2023 |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
