1. On bipartite (1,1,k)-mixed graphsCristina Dalfó, Grahame Erskine, Geoffrey Exoo, Miquel Àngel Fiol, James Tuite, 2025, original scientific article Abstract: 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.
Keywords: mixed graph, degree/diameter problem, Moore bound, bipartite graph
Published in RUP: 03.11.2025; Views: 405; Downloads: 0
 Full text (628,98 KB) |
2. Totally regular mixed graphs constructed from the CD(n,q) graphs of Lazebnik, Ustimenko and WoldarTatiana Jajcayova, Robert Jajcay, 2025, original scientific article Abstract: The CD(n,q) graphs are connected components of q-regular graphs D(n,q) introduced in 1995 by Lazebnik and Ustimenko. They constitute the best universal family of regular graphs of prime power degree with regard to the Cage Problem which calls for determining the orders of the smallest k-regular graphs of girth g. The girths of the CD(n,q) graphs are known to be at least n+4 in case of even n, and n+5 for odd n. We propose to extend the use of the CD(n,q) graphs into the area of mixed graphs by adding directions to certain edges of the C(n,q)graphs.
In the context of mixed graphs, graphs in which the number of incident non-oriented edges is the same for all vertices, and the numbers of out-going and in-going edges are also equal and the same for all vertices, are of special interest and are called totally regular mixed graphs. In view of the special properties of the original C(n,q) graphs with regard to cages, we believe that the totally regular mixed graphs we propose to study may also prove to be extremal with regard to properties sought for in the area of mixed graphs.
Keywords: cage problem, girth, degree, mixed graphs
Published in RUP: 03.11.2025; Views: 263; Downloads: 2
Full text (574,95 KB) |
3. The extremal generalised Randić index for a given degree rangeJohn Haslegrave, 2025, original scientific article Abstract: O and Shi proved that the Randić index of any graph G with minimum degree at least δ and maximum degree at most Δ is at least sqrt(δΔ)/(δ+Δ) |G|, with equality if and only if the graph is (δ, Δ)-biregular. In this note we give a short proof via a more general statement. As an application of our more general result, we classify for any given degree range which graphs minimise (or maximise) the generalised Randić index for any exponent, and describe the transitions between different types of behaviour precisely.
Keywords: Randić index, bounded-degree graph, extremal problem
Published in RUP: 03.11.2025; Views: 280; Downloads: 1
Full text (403,78 KB) |
4. |
5. A ▫$C^s$▫-smooth mixed degree and regularity isogeometric spline space over planar multi-patch domainsMario Kapl, Aljaž Kosmač, Vito Vitrih, 2026, original scientific article Abstract: We construct over a given bilinear multi-patch domain a novel $C^s$-smooth mixed degree and regularity isogeometric spline space, which possesses the degree $p=2s+1$ and regularity $r=s$ in a small neighborhood around the edges and vertices, and the degree~$\widetilde{p} \leq p$ with regularity $\widetilde{r} = \widetilde{p}-1 \geq r$ in all other parts of the domain. Our proposed approach relies on the technique Kapl and Vitrih (2021), which requires for the $C^s$-smooth isogeometric spline space a degree at least $p=2s+1$ on the entire multi-patch domain. Similar to Kapl and Vitrih (2021), the $C^s$-smooth mixed degree and regularity spline space is generated as the span of basis functions that correspond to the individual patches, edges and vertices of the domain. The reduction of degrees of freedom for the functions in the interior of the patches is achieved by introducing an appropriate mixed degree and regularity underlying spline space over $[0,1]^2$ to define the functions on the single patches. We further extend our construction with a few examples to the class of bilinear-like $G^8$ multi-patch parameterizations (Kapl and Vitrih (2018); Kapl and Vitrih (2021)), which enables the design of multi-patch domains having curved boundaries and interfaces. Finally, the great potential of the $C^8$-smooth mixed degree and regularity isogeometric spline space for performing isogeometric analysis is demonstrated by several numerical examples of solving two particular high order partial differential equations, namely the biharmonic and triharmonic equation, via the isogeometric Galerkin method.
Keywords: isogeometric analysis, Galerkin method, C^s-smoothness, mixed degree and regularity spline space, multi-patch domain
Published in RUP: 01.07.2025; Views: 669; Downloads: 4
Full text (3,76 MB)
This document has more files! More... |
6. A note on girth-diameter cagesGabriela Araujo-Pardo, Marston D. E. Conder, Natalia García-Colín, György Kiss, Dimitri Leemans, 2025, original scientific article Abstract: 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.
Keywords: cages, girth, degree-diameter problem
Published in RUP: 10.06.2025; Views: 721; Downloads: 15
Full text (378,53 KB)
This document has more files! More... |
7. |
8. |
9. |
10. |
