On the Boolean dimension of a graph and other related parameters

MaRDI QIDQ5038202zbMATH OpenFDO

Authors Maurice Pouzet, Hamza Si Kaddour, Bhalchandra D. Thatte

Publication date 30 September 2022

Full work available at URL https://arxiv.org/abs/2105.00206, https://dmtcs.episciences.org/10076

zbMATH Keywords

Boolean sumgeometric dimensioninversion indexsymplectic dimensiontournaments

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph operations (line graphs, products, etc.) (05C76) Graph theory (05C99)

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.

Recommendations

• Boolean dimension and tree-width
• scientific article; zbMATH DE number 3895118
• Boolean dimension and local dimension
• Boolean-width of graphs
• Comparing Dushnik-Miller dimension, Boolean dimension and local dimension

Cited in

(10)

• On the capacity of Boolean graph formulæ
• scientific article; zbMATH DE number 3895118 (Why is no real title available?)
• On metric dimension of Boolean graph BG₁(G)
• Invertibility of Digraphs and Tournaments
• On the minimum number of inversions to make a digraph k-(arc-)strong
• On tournament inversion
• On the minimum number of inversions to make a digraph k-(arc-)strong (extended abstract)
• A note on the invertibility of oriented graphs
• Problems, proofs, and disproofs on the inversion number
• Boolean-width of graphs

This page was built for publication: On the Boolean dimension of a graph and other related parameters

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5038202)