On the Boolean dimension of a graph and other related parameters

2021/05/01 by Pouzet, Maurice, Kaddour, Hamza Si, Thatte, Bhalchandra D.
#06A6 #06F15 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2105.00206

Abstract

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.

Related

• A New Definition of the Dimension of Graphs
• Comparing Dushnik-Miller Dimension, Boolean Dimension and Local\n Dimension
• On the strong metric dimension of the zero-divisor graph of a lattice
• Metric dimension related parameters in graphs: A survey on combinatorial, computational and applied results
• On the boolean-width of a graph: structure and applications