Conformality of Minimal Transversals of Maximal Cliques
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913904700948480 |
|---|---|
| author | Boros, Endre Gurvich, Vladimir Milanič, Martin Tikhanovsky, Dmitry Uno, Yushi |
| author_facet | Boros, Endre Gurvich, Vladimir Milanič, Martin Tikhanovsky, Dmitry Uno, Yushi |
| contents | Given a hypergraph $H$, the dual hypergraph of $H$ is the hypergraph of all minimal transversals of $H$. A hypergraph is conformal if it is the family of maximal cliques of a graph. In a recent work, Boros, Gurvich, Milanič, and Uno (Journal of Graph Theory, 2025) studied conformality of dual hypergraphs and proved several results related to this property, leading in particular to a polynomial-time algorithm for recognizing graphs in which all minimal transversals of maximal cliques have size at most $k$, for any fixed $k$. In this follow-up work, we provide a novel aspect to the study of graph clique transversals, by considering the dual conformality property from the perspective of graphs. More precisely, we study graphs for which the family of minimal transversals of maximal cliques is conformal. Such graphs are called clique dually conformal (CDC for short). It turns out that the class of CDC graphs is a rich generalization of the class of $P_4$-free graphs. As our main results, we completely characterize CDC graphs within the families of triangle-free graphs and split graphs. Both characterizations lead to polynomial-time recognition algorithms. Generalizing the fact that every $P_4$-free graph is CDC, we also show that the class of CDC graphs is closed under substitution, in the strong sense that substituting a graph $H$ for a vertex of a graph $G$ results in a CDC graph if and only if both $G$ and $H$ are CDC. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_10789 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Conformality of Minimal Transversals of Maximal Cliques Boros, Endre Gurvich, Vladimir Milanič, Martin Tikhanovsky, Dmitry Uno, Yushi Combinatorics Discrete Mathematics Data Structures and Algorithms 05C75, 05C69 (Primary) 05C65, 05D15, 05C85 (Secondary) Given a hypergraph $H$, the dual hypergraph of $H$ is the hypergraph of all minimal transversals of $H$. A hypergraph is conformal if it is the family of maximal cliques of a graph. In a recent work, Boros, Gurvich, Milanič, and Uno (Journal of Graph Theory, 2025) studied conformality of dual hypergraphs and proved several results related to this property, leading in particular to a polynomial-time algorithm for recognizing graphs in which all minimal transversals of maximal cliques have size at most $k$, for any fixed $k$. In this follow-up work, we provide a novel aspect to the study of graph clique transversals, by considering the dual conformality property from the perspective of graphs. More precisely, we study graphs for which the family of minimal transversals of maximal cliques is conformal. Such graphs are called clique dually conformal (CDC for short). It turns out that the class of CDC graphs is a rich generalization of the class of $P_4$-free graphs. As our main results, we completely characterize CDC graphs within the families of triangle-free graphs and split graphs. Both characterizations lead to polynomial-time recognition algorithms. Generalizing the fact that every $P_4$-free graph is CDC, we also show that the class of CDC graphs is closed under substitution, in the strong sense that substituting a graph $H$ for a vertex of a graph $G$ results in a CDC graph if and only if both $G$ and $H$ are CDC. |
| title | Conformality of Minimal Transversals of Maximal Cliques |
| topic | Combinatorics Discrete Mathematics Data Structures and Algorithms 05C75, 05C69 (Primary) 05C65, 05D15, 05C85 (Secondary) |
| url | https://arxiv.org/abs/2405.10789 |