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: 413; Prenosov: 0
 Celotno besedilo (628,98 KB) |
2. A note on girth-diameter cagesGabriela Araujo-Pardo, Marston D. E. Conder, Natalia García-Colín, György Kiss, Dimitri Leemans, 2025, izvirni znanstveni članek Opis: In this paper we introduce a problem closely related to the Cage Problem and the Degree Diameter Problem. For integers k ≥ 2, g ≥ 3 and d ≥ 1, we define a (k; g, d)-graph to be a k-regular graph with girth g and diameter d. We denote by n₀(k; g, d) the smallest possible order of such a graph, and, if such a graph exists, we call it a (k; g, d)-cage. In particular, we focus on (k; 5, 4)-graphs. We show that n₀(k; 5, 4) ≥ k² + k + 2 for all k, and report on the determination of all (k; 5, 4)-cages for k = 3, 4 and 5 and of examples with k = 6, and describe some examples of (k; 5, 4)-graphs which prove that n₀(k; 5, 4) ≤ 2k² for infinitely many k.
Ključne besede: cages, girth, degree-diameter problem
Objavljeno v RUP: 10.06.2025; Ogledov: 727; Prenosov: 15
Celotno besedilo (378,53 KB)
Gradivo ima več datotek! Več... |
3. |
4. |
5. O ekstremnih grafih z dano stopnjo in premerom/ožino : doktorska disertacijaSlobodan Filipovski, 2018, doktorska disertacija Ključne besede: adjacency matrix, antipodal graphs, cages, excess, defect, Ramanujan graphs, selfrepeats, degree/diameter problem, spectrum, Moore graphs, asymptotic density, distance matrices, Bermond and Bollobas problem
Objavljeno v RUP: 21.01.2019; Ogledov: 5293; Prenosov: 0 |
6. A note on a geometric construction of large Cayley graps of given degree and diameterGyörgy Kiss, István Kovács, Klavdija Kutnar, János Ruff, Primož Šparl, 2009, izvirni znanstveni članek Opis: An infinite series and some sporadic examples of large Cayley graphs with given degree and diameter are constructed. The graphs arise from arcs, caps and other objects of finite projective spaces.
Ključne besede: degree, diameter problem, Moore bound, finite projective spaces
Objavljeno v RUP: 15.10.2013; Ogledov: 18622; Prenosov: 81
 Povezava na celotno besedilo |
7. |
