1. On bipartite (1,1,k)-mixed graphsCristina Dalfó, Grahame Erskine, Geoffrey Exoo, Miquel Àngel Fiol, James Tuite, 2025, izvirni znanstveni članek Opis: Mixed graphs can be seen as digraphs that have both arcs and edges (or digons, that is, two opposite arcs). In this paper, we consider the case where such graphs are bipartite and in which the undirected and directed degrees are one. The best graphs, in terms of the number of vertices, are presented for small diameters. Moreover, two infinite families of such graphs with diameter k and number of vertices of the order of 2k/2 are proposed, one of them being totally regular (1,1)-mixed graphs. In addition, we present two more infinite families called chordal ring and chordal double ring mixed graphs, which are bipartite and related to tessellations of the plane. Finally, we give an upper bound that improves the Moore bound for bipartite mixed graphs for r = z = 1.
Ključne besede: mixed graph, degree/diameter problem, Moore bound, bipartite graph
Objavljeno v RUP: 03.11.2025; Ogledov: 108; Prenosov: 0
 Celotno besedilo (628,98 KB) |
2. Mutual-visibility problems in Kneser and Johnson graphsGülnaz Boruzanlı Ekinci, Csilla Bujtás, 2025, izvirni znanstveni članek Opis: Let G be a connected graph and X ⊆ V(G). By definition, two vertices u and v are X-visible in G if there exists a shortest u, v-path with all internal vertices being outside of the set X. The largest size of X such that any two vertices of G (resp. any two vertices from X) are X-visible is the total mutual-visibility number (resp. the mutual-visibility number) of G.
In this paper, we determine the total mutual-visibility number of Kneser graphs, bipartite Kneser graphs, and Johnson graphs. The formulas proved for Kneser, and bipartite Kneser graphs are related to the size of transversal-critical uniform hypergraphs, while the total mutual-visibility number of Johnson graphs is equal to a hypergraph Turán number. Exact values or estimations for the mutual-visibility number over these graph classes are also established.
Ključne besede: mutual-visibility set, total mutual-visibility set, Kneser graph, bipartite Kneser graph, Johnson graph, Turán-type problem, covering design
Objavljeno v RUP: 22.10.2025; Ogledov: 152; Prenosov: 1
Celotno besedilo (426,16 KB) |
3. On relationships between treewidth, clique number, tree-independence number, and induced minors : master’s thesisÐorđe Vasić, 2025, magistrsko delo Ključne besede: treewidth, clique number, tree-independence number, induced minor, hered itary graph class, bipartite chain graph
Objavljeno v RUP: 11.09.2025; Ogledov: 231; Prenosov: 5
Celotno besedilo (839,36 KB) |
4. |
5. |
6. |
7. |
8. Bipartite graphs of small readabilityRayan Chikhi, Vladan Jovičić, Stefan Kratsch, Paul Medvedev, Martin Milanič, Sofya Raskhodnikova, Nithin Varma, 2019, izvirni znanstveni članek Ključne besede: bipartite graph, readability, bipartite chain graph, polynomial-time algorithm, grid graph
Objavljeno v RUP: 26.07.2019; Ogledov: 3147; Prenosov: 103
 Povezava na celotno besedilo |
9. |
10. Bipartite graphs of small readabilityRayan Chikhi, Vladan Jovičić, Stefan Kratsch, Paul Medvedev, Martin Milanič, Sofya Raskhodnikova, Nidhi Varma Srivastava, 2018, objavljeni znanstveni prispevek na konferenci Ključne besede: bipartite graph, readability, bipartite chain graph, polynomial-time algorithm, grid graph
Objavljeno v RUP: 17.09.2018; Ogledov: 3845; Prenosov: 72
Povezava na celotno besedilo |
