1. Distance-regular Cayley graphs over ℤpˢ ⊕ ℤpXiongfeng Zhan, Lu Lu, Xueyi Huang, 2025, izvirni znanstveni članek Opis: In 2007, Miklavič and Potočnik proposed the problem of characterizing distance-regular Cayley graphs, which can be viewed as an extension of the problem of identifying strongly regular Cayley graphs, or equivalently, regular partial difference sets. Let p be an odd prime. In this paper, all distance-regular Cayley graphs over ℤps ⊕ ℤp are identified. It is shown that every such graph is isomorphic to a complete graph, a complete multipartite graph, or the line graph of a transversal design TD(r, p) with 2 ≤ r ≤ p − 1.
Ključne besede: distance-regular graph, Cayley graph, Schur ring, Fourier transformation, transversal design
Objavljeno v RUP: 21.10.2025; Ogledov: 286; Prenosov: 1
 Celotno besedilo (461,23 KB) |
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: 248; Prenosov: 4
Celotno besedilo (475,86 KB)
Gradivo ima več datotek! Več... |
3. 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: 3232; Prenosov: 134
 Povezava na celotno besedilo |
4. Nove karakterizacije v strukturni teoriji grafov : 1-popolno usmerljivi grafi, produktni grafi in cena povezanostiTatiana Romina Hartinger, 2017, doktorska disertacija Ključne besede: 1-perfectly orientable graph, structural characterization of families of graphs, chordal graph, interval graph, circular arc graph, cograph, block-cactus graph, cobipartite graph, K4-minor-free graph, outerplanar graph, graph product, Cartesian product, lexicographic product, direct product, strong product, price of connectivity, cycle transversal, path transversal
Objavljeno v RUP: 09.11.2017; Ogledov: 5252; Prenosov: 44
Povezava na celotno besedilo |
5. |
6. |
