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: 32; Downloads: 2
 Full text (677,80 KB)
This document has more files! More... |
2. On regular graphs with Šoltés verticesNino Bašić, Martin Knor, Riste Škrekovski, 2025, original scientific article Abstract: Let ▫$W(G)$▫ be the Wiener index of a graph ▫$G$▫. We say that a vertex ▫$v \in V(G)$▫ is a Šoltés vertex in ▫$G$▫ if ▫$W(G - v) = W(G)$▫, i.e. the Wiener index does not change if the vertex ▫$v$▫ is removed. In 1991, Šoltés posed the problem of identifying all connected graphs ▫$G$▫ with the property that all vertices of ▫$G$▫ are Šoltés vertices. The only such graph known to this day is ▫$C_{11}$▫. As the original problem appears to be too challenging, several relaxations were studied: one may look for graphs with at least ▫$k$▫ Šoltés vertices; or one may look for ▫$\alpha$▫-Šoltés graphs, i.e. graphs where the ratio between the number of Šoltés vertices and the order of the graph is at least ▫$\alpha$▫. Note that the original problem is, in fact, to find all ▫$1$▫-Šoltés graphs. We intuitively believe that every ▫$1$▫-Šoltés graph has to be regular and has to possess a high degree of symmetry. Therefore, we are interested in regular graphs that contain one or more Šoltés vertices. In this paper, we present several partial results. For every ▫$r\ge 1$▫ we describe a construction of an infinite family of cubic ▫$2$▫-connected graphs with at least ▫$2^r$▫ Šoltés vertices. Moreover, we report that a computer search on publicly available collections of vertex-transitive graphs did not reveal any ▫$1$▫-Šoltés graph. We are only able to provide examples of large ▫$\frac{1}{3}$▫-Šoltés graphs that are obtained by truncating certain cubic vertex-transitive graphs. This leads us to believe that no ▫$1$▫-Šoltés graph other than ▫$C_{11}$▫ exists.
Keywords: Šoltés problem, Wiener index, regular graphs, cubic graphs, Cayley graph, Šoltés vertex
Published in RUP: 10.09.2025; Views: 378; Downloads: 2
Full text (456,75 KB) |
3. Selected topics on Wiener indexMartin Knor, Riste Škrekovski, Aleksandra Tepeh, 2024, original scientific article Keywords: graph distance, Wiener index, average distance, topological index, molecular descriptor, chemical graph theory
Published in RUP: 26.05.2025; Views: 753; Downloads: 7
Full text (516,10 KB) |
4. Some remarks on Balaban and sum-Balaban indexMartin Knor, Jozef Komorník, Riste Škrekovski, Aleksandra Tepeh, 2020, original scientific article Abstract: In the paper we study maximal values of Balaban and sum-Balaban index, and correct some results appearing in the literature which are only partially correct. Henceforth, we were able to solve a conjecture of M. Aouchiche, G. Caporossi and P. Hansen regarding the comparison of Balaban and Randić index. In addition, we showed that for every k and large enough n, the first k graphs of order n with the largest value of Balaban index are trees. We conclude the paper with a result about the accumulation points of sum-Balaban index.
Keywords: topological index, Balaban index, sum-Balaban index, Randić index
Published in RUP: 03.01.2022; Views: 2464; Downloads: 24
Full text (310,27 KB) |
5. |
6. Total positivity of Toeplitz matrices of recursive hypersequencesTomislav Došlić, Ivica Martinjak, Riste Škrekovski, 2019, original scientific article Keywords: total positivity, totally positive matrix, Toeplitz matrix, Hankel matrix, hyperfibonacci sequence, log-concavity
Published in RUP: 03.01.2022; Views: 2007; Downloads: 32
Full text (254,44 KB) |
7. A note on acyclic number of planar graphsMirko Petruševski, Riste Škrekovski, 2017, original scientific article Abstract: The acyclic number ▫$a(G)$▫ of a graph ▫$G$▫ is the maximum order of an induced forest in ▫$G$▫. The purpose of this short paper is to propose a conjecture that ▫$a(G)\geq \left( 1-\frac{3}{2g}\right)n$▫ holds for every planar graph ▫$G$▫ of girth ▫$g$▫ and order ▫$n$▫, which captures three known conjectures on the topic. In support of this conjecture, we prove a weaker result that ▫$a(G)\geq \left( 1-\frac{3}{g} \right)n$▫ holds. In addition, we give a construction showing that the constant ▫$\frac{3}{2}$▫ from the conjecture cannot be decreased.
Keywords: induced forest, acyclic number, planar graph, girth
Published in RUP: 03.01.2022; Views: 2156; Downloads: 22
Full text (227,50 KB) |
8. Relative edge betweenness centralityDamir Vukičević, Riste Škrekovski, Aleksandra Tepeh, 2017, original scientific article Abstract: We introduce a new edge centrality measure - relative edge betweenness ▫$\gamma (uv) = b(uv)/\sqrt{c(u)c(v)}$▫, where ▫$b(uv$)▫ is the standard edge betweenness and ▫$c(u)$▫ is the adjusted vertex betweenness. In this alternative definition, the importance of an edge is normalized with respect to the importance of its end-vertices. This gives a better presentation of the ''local'' importance of an edge, i.e. its importance in the near neighborhood. We present sharp upper and lower bounds on this invariant together with the characterization of graphs attaining these bounds. In addition, we discuss the bounds for various interesting graph families, and state several open problems.
Published in RUP: 03.01.2022; Views: 1922; Downloads: 20
Full text (261,26 KB) |
9. Mathematical aspects of fullerenesVesna Andova, František Kardoš, Riste Škrekovski, 2016, original scientific article Abstract: Fullerene graphs are cubic, 3-connected, planar graphs with exactly 12 pentagonal faces, while all other faces are hexagons. Fullerene graphs are mathematical models of fullerene molecules, i.e., molecules comprised only by carbon atoms different than graphites and diamonds. We give a survey on fullerene graphs from our perspective, which could be also considered as an introduction to this topic. Different types of fullerene graphs are considered, their symmetries, and construction methods. We give an overview of some graph invariants that can possibly correlate with the fullerene molecule stability, such as: the bipartite edge frustration, the independence number, the saturation number, the number of perfect matchings, etc.
Keywords: fullerene, cubic graph, planar graph, topological indices
Published in RUP: 03.01.2022; Views: 2444; Downloads: 21
Full text (626,25 KB) |
10. Mathematical aspects of Wiener indexMartin Knor, Riste Škrekovski, Aleksandra Tepeh, 2016, original scientific article Abstract: The Wiener index (i.e., the total distance or the transmission number), defined as the sum of distances between all unordered pairs of vertices in a graph, is one of the most popular molecular descriptors. In this article we summarize some results, conjectures and problems on this molecular descriptor, with emphasis on works we were involved in.
Keywords: Wiener index, total distance, topological index, molecular descriptor, chemical graph theory
Published in RUP: 03.01.2022; Views: 3839; Downloads: 49
Full text (434,58 KB) |
