Geodesic
Hypergraphs with Polynomial Representation: Introducing $r$-splits
Discrete mathematics & theoretical computer science, special issue ICGT'22, Tome 25 (2023-2024) no. 3.

Voir la notice de l'article provenant de la source Episciences

Inspired by the split decomposition of graphs and rank-width, we introduce the notion of $r$-splits. We focus on the family of $r$-splits of a graph of order $n$, and we prove that it forms a hypergraph with several properties. We prove that such hypergraphs can be represented using only $\mathcal O(n^{r+1})$ of its hyperedges, despite its potentially exponential number of hyperedges. We also prove that there exist hypergraphs that need at least $\Omega(n^r)$ hyperedges to be represented, using a generalization of set orthogonality.
DOI : 10.46298/dmtcs.10751
Classification : 05C31, 05C62, 05C65, 05C70 
@article{DMTCS_2024_25_3_a3,
     author = {Pitois, Fran\c{c}ois and Haddad, Mohammed and Seba, Hamida and Togni, Olivier},
     title = {Hypergraphs with {Polynomial} {Representation:} {Introducing} $r$-splits},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {25},
     number = {3},
     year = {2023-2024},
     doi = {10.46298/dmtcs.10751},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.10751/}
}
TY  - JOUR
AU  - Pitois, François
AU  - Haddad, Mohammed
AU  - Seba, Hamida
AU  - Togni, Olivier
TI  - Hypergraphs with Polynomial Representation: Introducing $r$-splits
JO  - Discrete mathematics & theoretical computer science
PY  - 2023-2024
VL  - 25
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.10751/
DO  - 10.46298/dmtcs.10751
LA  - en
ID  - DMTCS_2024_25_3_a3
ER  - 
%0 Journal Article
%A Pitois, François
%A Haddad, Mohammed
%A Seba, Hamida
%A Togni, Olivier
%T Hypergraphs with Polynomial Representation: Introducing $r$-splits
%J Discrete mathematics & theoretical computer science
%D 2023-2024
%V 25
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.10751/
%R 10.46298/dmtcs.10751
%G en
%F DMTCS_2024_25_3_a3
Pitois, François; Haddad, Mohammed; Seba, Hamida; Togni, Olivier. Hypergraphs with Polynomial Representation: Introducing $r$-splits. Discrete mathematics & theoretical computer science, special issue ICGT'22, Tome 25 (2023-2024) no. 3. doi : 10.46298/dmtcs.10751. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.10751/

Cité par Sources :