1. Type-based computation of knowledge graph statisticsIztok Savnik, Kiyoshi Nitta, Riste Škrekovski, Nikolaus Augsten, 2025, original scientific article Abstract: We propose a formal model of a knowledge graph (abbr. KG) that classifies the ground triples into sets that correspond to the triple types. The triple types are partially ordered by the sub-type relation. Consequently, the sets of ground triples that are the interpretations of triple types are partially ordered by the subsumption relation. The types of triple patterns restrict the sets of ground triples, which need to be addressed in the evaluation of triple patterns, to the interpretation of the types of triple patterns. Therefore, a schema graph of a KG should include all triple types that are likely to be determined as the types of triple patterns. The stored schema graph consists of the selected triple types that are stored in a KG and the complete schema graph includes all valid triple types of KG. We propose choosing the schema graph, which consists of the triple types from a strip around the stored schema graph, i.e., the triple types from the stored schema graph and some adjacent levels of triple types with respect to the sub-type relation. Given a selected schema graph, the statistics are updated for each ground triple t from a KG. First, we determine the set of triple types stt from the schema graph that are affected by adding a triple t to an RDF store. Finally, the statistics of triple types from the set stt are updated.
Keywords: knowledge graphs, RDF stores, graph database systems
Published in RUP: 16.01.2026; Views: 304; Downloads: 2
 Full text (677,80 KB)
This document has more files! More... |
2. Automorphisms and quotients of 2-colored quasi best match graphsAnnachiara Korchmaros, 2026, original scientific article Abstract: 2-colored quasi best match graphs (2-qBMGs) are directed graphs that arose in evolution theory. Investigations of 2-qBMGs have mostly focused on computational issues. However, 2-qBMGs also have relevant properties for structural graph theory; in particular, their undirected underlying graph is free from induced paths and cycles of size at least 6. In this paper, results on the structure of the automorphism groups of 2-qBMGs are obtained, which shows how to construct 2-qBMGs with large automorphism groups.
Keywords: group of automorphisms, bipartite graphs, phylogenetics
Published in RUP: 05.01.2026; Views: 382; Downloads: 1
Full text (498,12 KB) |
3. On the leaves of graph search treesRobert Scheffler, 2026, original scientific article Abstract: Graph searches and their respective search trees are widely used in algorithmic graph theory. The problem whether a given spanning tree can be a graph search tree has been considered for different searches, graph classes and search tree paradigms. Similarly, the question whether a particular vertex can be visited last by some search has been studied extensively in recent years. We combine these two problems by considering the question whether a vertex can be a leaf of a graph search tree. We show that for particular search trees, including DFS trees, this problem is easy if we allow the leaf to be the first vertex of the search ordering. We contrast this result by showing that the problem becomes hard for many searches, including DFS and BFS, if we forbid the leaf to be the first vertex. Additionally, we present several structural and algorithmic results for search tree leaves of chordal graphs.
Keywords: graph search, graph search trees, leaves, chordal graphs
Published in RUP: 21.12.2025; Views: 246; Downloads: 2
Full text (515,71 KB) |
4. A classification of Q-polynomial distance-regular graphs with girth 6Štefko Miklavič, 2025, original scientific article Abstract: Let Γ denote a Q-polynomial distance-regular graph with diameter D and valency k≥3. In [Homotopy in Q-polynomial distance-regular graphs, Discrete Math., {\bf 223} (2000), 189–206], H. Lewis showed that the girth of Γ is at most 6. In this paper we classify graphs that attain this upper bound. We show that Γ has girth 6 if and only if it is either isomorphic to the Odd graph on a set of cardinality 2D+1, or to a generalized hexagon of order (1,k−1).
Keywords: distance-regular graphs, Q-polynomial property, girth
Published in RUP: 01.12.2025; Views: 1271; Downloads: 3
Full text (291,61 KB)
This document has more files! More... |
5. On (r,g,χ)- graphs and cages of regularity r, girth g and chromatic number χGabriela Araujo-Pardo, Julio César Díaz-Calderón, Julián Fresán-Figueroa, Diego González-Moreno, Linda Lesniak, Mika Olsen, 2025, original scientific article Abstract: For integers r ≥ 2, g ≥ 3 and χ ≥ 2, an (r, g, χ)-graph is an r-regular graph with girth g and chromatic number χ. Such a graph of minimum order is called an (r, g, χ)-cage. Here we prove the existence of (r, g, χ)-graphs for all r and even g when χ = 2 and for all r and g when χ = 3. Furthermore, using both existence proofs and explicit constructions we give examples of (r, g, χ)-graphs for infinitely many values of r, g, χ.
Keywords: graphs, cages, girth, chromatic number
Published in RUP: 03.11.2025; Views: 354; Downloads: 2
Full text (408,46 KB) |
6. 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: 304; Downloads: 2
Full text (574,95 KB) |
7. A sharp upper bound for the harmonious total chromatic number of graphs and multigraphsMarién Abreu, John Baptist Gauci, Davide Mattiolo, Giuseppe Mazzuoccolo, Federico Romaniello, Christian Rubio-Montiel, Tommaso Traetta, 2025, original scientific article Abstract: A proper total colouring of a graph G is called harmonious if it has the further property that when replacing each unordered pair of incident vertices and edgeswith their colours, then no pair of colours appears twice. The smallest number of colours for it to exist is called the harmonious total chromatic number of G, denoted by h_t(G). Here, we give a general upper bound for h_t(G) in terms of the order n of G. Our two main results are obvious consequences of the computation of the harmonious total chromatic number of the complete graph Kn and of the complete multigraph λK_n, where λ is the number of edges joining each pair of vertices of Kn. In particular, Araujo-Pardo et al. have recently shown that 3/2 n ≤ h_t(K_n)≤ 5/3 n + θ(1). In this paper, we prove that h_t(K_n) = ⌈3/2 n⌉ except for h_t(K₁) = 1 and h_t(K₄) = 7; therefore, h_t(G)≤ ⌈3/2 n⌉, for every graph G on n > 4 vertices. Finally, we extend such a result to the harmonious total chromatic number of the complete multigraph λKn and as a consequence show that h_t(G) ≤ (λ-1)(2⌈n/2⌉-1)+⌈3n/2⌉ for n > 4, where G is a multigraph such that λ is the maximum number of edges between any two vertices.
Keywords: total colouring, harmonious colouring, complete graphs, complete multigraphs, Levi graph
Published in RUP: 03.11.2025; Views: 373; Downloads: 13
Full text (387,22 KB) |
8. Groups with elements of order 8 do not have the DCI propertyTed Dobson, Joy Morris, Pablo Spiga, 2025, original scientific article Abstract: Let k be odd, and n an odd multiple of 3. Although this can also be deduced from known results, we provide a new proof that Ck ⋊ C₈ and (Cn × C₃) ⋊ C₈ do not have the Directed Cayley Isomorphism (DCI) property. When k is prime, Ck ⋊ C₈ had previously been proved to have the Cayley Isomorphism (CI) property. To the best of our knowledge, the groups Cp ⋊ C₈ (where p is an odd prime) are only the second known infinite family of groups that have the CI property but do not have the DCI property. This also provides a new proof of the result (which follows from known results but was not explicitly published) that no group with an element of order 8 has the DCI property.
One piece of our proof is a new result that may prove to be of independent interest: we show that if a permutation group has a regular subgroup of index 2 then it must be 2-closed.
Keywords: CI property, DCI property, Cayley graphs, Cayley digraphs, 2-closed groups, 2-closure
Published in RUP: 03.11.2025; Views: 301; Downloads: 1
Full text (344,18 KB) |
9. Primitive, edge-short, isometric, and pantochordal cyclesGover E. C. Guzman, Marcos E. González Laffitte, André Fujita, Peter F. Stadler, 2025, original scientific article Abstract: A cycle in a graph G is said to be primitive from its vertex x if at least one of its edges does not belong to any shorter cycle that passes through x. This type of cycle and an associated notion of extended neighborhoods play a key role in message-passing algorithms that compute spectral properties of graphs with short loops. Here, we investigate such primitive cycles and graphs without long primitive cycles in a more traditional graph-theoretic framework. We show that a cycle is primitive from all its vertices if and only if it is isometric. We call a cycle fully redundant cycles if it is not primitive from any of its vertices and show that fully redundant cycles, in particular, are not edge short, i.e., they cannot be represented as the edge-disjoint union of a single edge and two shortest paths in G. The families Rk and Lk of graphs with all cycles of length at least k + 1 being fully redundant and not edge-short, respectively, coincide for k = 3 and k = 4. In these graphs, all cycles of length at least k + 1 are pantochordal, i.e., each of their vertices is incident with a chord. None of these results generalizes to k ≥ 5. Moreover, R₃ = L₃ turn out to be the block graphs, and R₄ = L₄ are the graphs with complete multi-partite blocks. The cographs, finally, are shown to form a proper subset of R₅.
Keywords: edge-short cycle, chord, block-graph, complete multipartite graph, wheel graphs, cographs, geodesic cycles, Hamiltonian cycles
Published in RUP: 03.11.2025; Views: 280; Downloads: 1
Full text (478,50 KB) |
10. |
