 |
Discrete Mathematics & Theoretical Computer Science |
7437
Maurice Pouzet ; Hamza Si Kaddour ; Bhalchandra Thatte - On the Boolean dimension of a graph and other related parameters
dmtcs:7437 - Discrete Mathematics & Theoretical Computer Science, September 23, 2022, vol. 23 no. 2, special issue in honour of Maurice Pouzet - https://doi.org/10.46298/dmtcs.7437On the Boolean dimension of a graph and other related parameters
- 1 Université Claude Bernard Lyon 1
- 2 Universidade Federal de Minas Gerais = Federal University of Minas Gerais [Belo Horizonte, Brazil]
We present the Boolean dimension of a graph, we relate it with the notions of inner, geometric and symplectic dimensions, and with the rank and minrank of a graph. We obtain an exact formula for the Boolean dimension of a tree in terms of a certain star decomposition. We relate the Boolean dimension with the inversion index of a tournament.
Source: HAL:hal-03214095v4
Volume: vol. 23 no. 2, special issue in honour of Maurice Pouzet
Section: Special issues
Published on: September 23, 2022
Accepted on: August 2, 2022
Submitted on: May 3, 2021
Keywords: graphs,Boolean sum,symplectic dimension,geometric dimension,tournaments,inversion index,06A6, 06F15,[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
Funding:
- Source : OpenAIRE Graph
- PROJET AVENIR LYON SAINT-ETIENNE; Funder: French National Research Agency (ANR); Code: ANR-11-IDEX-0007
Consultation statistics
This page has been seen 220 times.
This article's PDF has been downloaded 116 times.