1. Conformality of minimal transversals of maximal cliquesEndre Boros, Vladimir Gurvich, Martin Milanič, Dmitry Tikhanovsky, Yushi Uno, 2026, izvirni znanstveni članek Opis: Given a hypergraph ℋ, the dual hypergraph of ℋis the hypergraph of all minimal transversals of ℋ. 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, for any fixed k, all minimal transversals of maximal cliques have size at most 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 P4-free graphs. As our main results, we completely 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 P4-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.
Ključne besede: maximal clique, minimal transversal, conformal hypergraph, triangle-free graph, split graph
Objavljeno v RUP: 16.12.2025; Ogledov: 196; Prenosov: 2
 Celotno besedilo (1,65 MB)
Gradivo ima več datotek! Več... |
2. Conformal hypergraphs : duality and implications for the upper clique transversal problemEndre Boros, Vladimir Gurvich, Martin Milanič, Yushi Uno, 2025, izvirni znanstveni članek Opis: 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.
Ključne besede: conformal hypergraph, dual hypergraph, hypergraph, maximal clique, upper clique transversal
Objavljeno v RUP: 25.09.2025; Ogledov: 322; Prenosov: 4
Celotno besedilo (475,86 KB)
Gradivo ima več datotek! Več... |
3. |
4. Sprague-Grundy function of matroids and related hypergraphsEndre Boros, Vladimir Gurvich, Nhan Bao Ho, Kazuhisa Makino, Peter Muršič, 2019, izvirni znanstveni članek Ključne besede: matroid, self-dual matroid, impartial game, Sprague-Grundy function, Nim, hypergraph Nim, JM hypergraph
Objavljeno v RUP: 11.02.2020; Ogledov: 2670; Prenosov: 105
 Povezava na celotno besedilo |
5. |
6. On the Sprague-Grundy function of Exact k-NimEndre Boros, Vladimir Gurvich, Nhan Bao Ho, Kazuhisa Makino, Peter Muršič, 2018, izvirni znanstveni članek Ključne besede: Moore's Nim, Exact Nim, impartial games, P-position, Sprague-Grundy function
Objavljeno v RUP: 22.05.2019; Ogledov: 3288; Prenosov: 129
Povezava na celotno besedilo |
7. Sprague-Grundy function of symmetric hypergraphsEndre Boros, Vladimir Gurvich, Nhan Bao Ho, Kazuhisa Makino, Peter Muršič, 2019, izvirni znanstveni članek Ključne besede: impartial games, Sprague-Grundy function, Nim, hypergraph Nim, JM formula, JM hypergraph, symmetric hypergraph, transversal-free hypergraph
Objavljeno v RUP: 22.05.2019; Ogledov: 3315; Prenosov: 134
Povezava na celotno besedilo |
8. A three-person deterministic graphical game without Nash equilibriaEndre Boros, Vladimir Gurvich, Martin Milanič, Vladimir Oudalov, Jernej Vičič, 2018, izvirni znanstveni članek Opis: We give an example of a three-person deterministic graphical game that has no Nash equilibrium in pure stationary strategies. The game has seven positions, four outcomes (a unique cycle and three terminal positions), and its normal form is of size only. Thus, the example strengthens significantly the one obtained in 2014 by Gurvich and Oudalov; the latter has four players, five terminals, and normal form of size . Furthermore, our example is minimal with respect to the number of players. Somewhat similar examples were known since 1975, but they were not related to deterministic graphical games. The small size of our example allows us to verify that it has no Nash equilibrium not only in pure but also in independently mixed (so-called behavioral) strategies. For independently mixed strategies two distinct effective payoffs can be considered: along with the classical Markovian evaluation, we also consider a priori evaluation, which may be a better fit for playing in behavioral strategies
Ključne besede: deterministic graphical multi-person game, perfect information, Nash equilibrium, directed cycle, terminal position, pure stationary strategy
Objavljeno v RUP: 30.03.2018; Ogledov: 5545; Prenosov: 179
Povezava na celotno besedilo |
9. |
10. |
