1. Conformal hypergraphs : duality and implications for the upper clique transversal problemEndre Boros, Vladimir Gurvich, Martin Milanič, Yushi Uno, 2025, original scientific article Abstract: Given a hypergraph H, the dual hypergraph of H is the hypergraph of all minimal transversals of H. The dual hypergraph is always Sperner, that is, no hyperedge contains another. A special case of Sperner hypergraphs are the conformal Sperner hypergraphs, which correspond to the families of maximal cliques of graphs. All these notions play an important role in many fields of mathematics and computer science, including combinatorics, algebra, database theory, etc. In this paper we study conformality of dual hypergraphs and prove several results related to the problem of recognizing this property. In particular, we show that the problem is in co-NP and can be solved in polynomial time for hypergraphs of bounded dimension. In the special case of dimension 3, we reduce the problem to 2-Satisfiability. Our approach has an implication in algorithmic graph theory: we obtain a polynomial-time algorithm for recognizing graphs in which all minimal transversals of maximal cliques have size at most k, for any fixed k.
Keywords: conformal hypergraph, dual hypergraph, hypergraph, maximal clique, upper clique transversal
Published in RUP: 25.09.2025; Views: 1003; Downloads: 5
 Full text (475,86 KB)
This document has more files! More... |
2. The distance function on Coxeter-like graphs and self-dual codesMarko Orel, Draženka Višnjić, 2025, original scientific article Keywords: Coxeter graph, invertible symmetric matrices, binary field, rank, distance in graphs, alternate matrices, self-dual codes
Published in RUP: 30.05.2025; Views: 1096; Downloads: 18
Full text (1,26 MB)
This document has more files! More... |
3. |
4. |
5. Načrti in Hadamardove matrike : zaključna nalogaMateja Grižon, 2020, undergraduate thesis Keywords: t-načrt, končna projektivna ravnina, Steinerjev sistem, incidenčna matrika, simetrični načrt, dual načrta, permutacijska grupa, avtomorzem načrta, skrčitev načrta, razširitev načrta, Hadamardova matrika, Hadamardov načrt
Published in RUP: 02.10.2020; Views: 2893; Downloads: 31
 Link to full text
This document has more files! More... |
6. Qiao, Zhi, Koolen, Jack: A new characterization of the dual polar graphs. (English summary). - J. Combin. Theory Ser. B 135 (2019), 200-211Safet Penjić, 2020, review, book review, critique Keywords: Distance-regular graph, dual polar graph, Delsarte clique
Published in RUP: 15.04.2020; Views: 4058; Downloads: 18
Link to full text |
7. Sprague-Grundy function of matroids and related hypergraphsEndre Boros, Vladimir Gurvich, Nhan Bao Ho, Kazuhisa Makino, Peter Muršič, 2019, original scientific article Keywords: matroid, self-dual matroid, impartial game, Sprague-Grundy function, Nim, hypergraph Nim, JM hypergraph
Published in RUP: 11.02.2020; Views: 3016; Downloads: 106
Link to full text |
8. |
9. Mamart, Siwaporn: A group commutator involving the last distance matrix and dual distance matrix of a Q-polynomial distance-regular graph: the Hamming graph case. - Graphs Combin. 34 (2018), no. 4, 803--817Safet Penjić, 2018, review, book review, critique Keywords: distance-regular graph, Q-polynomial, distance matrix, dual distance matrix
Published in RUP: 21.01.2019; Views: 3112; Downloads: 18
Link to full text |
10. Experimental and numerical studies of CFRP tube and steel spiral dual-confined concrete composite columns under axial impact loadingLiang Huang, Chang Gao, Libo Yan, Tao Yu, Bohumil Kasal, 2018, original scientific article Keywords: CFRP tube, spiral reinforcement, dual-confinement, axial impact resistance, cracking resistance, ductile failure, dynamic increase factor, finite element analysis
Published in RUP: 19.11.2018; Views: 3642; Downloads: 227
Link to full text |
