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.7437
On the Boolean dimension of a graph and other related parametersArticle

Authors: Maurice Pouzet 1,2,3; Hamza Si Kaddour 1,2,3; Bhalchandra Thatte 4

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.

https://doi.org/10.46298/dmtcs.7437
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
  • Funder: French National Research Agency (ANR); Code: ANR-11-IDEX-0007

2 Documents citing this article

Share and export

Consultation statistics

This page has been seen 576 times.
This article's PDF has been downloaded 519 times.