21. On orders of automorphisms of vertex-transitive graphsPrimož Potočnik, Micael Toledo, Gabriel Verret, 2024, izvirni znanstveni članek Povzetek: In this paper we investigate orders, longest cycles and the number of cycles of automorphisms of finite vertex-transitive graphs. In particular, we show that the order of every automorphism of a connected vertex-transitive graph with $n$ vertices and of valence $d$, $d\le 4$, is at most $c_d n$ where $c_3=1$ and $c_4 = 9$. Whether such a constant $c_d$ exists for valencies larger than $4$ remains an unanswered question. Further, we prove that every automorphism $g$ of a finite connected $3$-valent vertex-transitive graph $\Gamma$, $\Gamma \not\cong K_{3,3}$, has a regular orbit, that is, an orbit of $\langle g \rangle$ of length equal to the order of $g$. Moreover, we prove that in this case either $\Gamma$ belongs to a well understood family of exceptional graphs or at least $5/12$ of the vertices of $\Gamma$ belong to a regular orbit of $g$. Finally, we give an upper bound on the number of orbits of a cyclic group of automorphisms $C$ of a connected $3$-valent vertex-transitive graph $\Gamma$ in terms of the number of vertices of $\Gamma$ and the length of a longest orbit of $C$. Ključne besede: graphs, automorphism groups, vertex-transitive, regular orbit, cubic, tetravalent Objavljeno v DiRROS: 19.02.2024; Ogledov: 413; Prenosov: 171 Celotno besedilo (573,20 KB) Gradivo ima več datotek! Več... |
22. Strong edge geodetic problem on complete multipartite graphs and some extremal graphs for the problemSandi Klavžar, Eva Zmazek, 2024, izvirni znanstveni članek Povzetek: A set of vertices $X$ of a graph $G$ is a strong edge geodetic set if to any pair of vertices from $X$ we can assign one (or zero) shortest path between them such that every edge of $G$ is contained in at least one on these paths. The cardinality of a smallest strong edge geodetic set of $G$ is the strong edge geodetic number ${\rm sg_e}(G)$ of $G$. In this paper, the strong edge geodetic number of complete multipartite graphs is determined. Graphs $G$ with ${\rm sg_e}(G) = n(G)$ are characterized and ${\rm sg_e}$ is determined for Cartesian products $P_n\,\square\, K_m$. The latter result in particular corrects an error from the literature. Ključne besede: strong edge geodetic problem, complete multipartite graph, edge-coloring, Cartesian product of graphs Objavljeno v DiRROS: 19.02.2024; Ogledov: 351; Prenosov: 143 Celotno besedilo (430,75 KB) Gradivo ima več datotek! Več... |
23. Resolvability and convexity properties in the Sierpiński product of graphsMichael A. Henning, Sandi Klavžar, Ismael G. Yero, 2024, izvirni znanstveni članek Povzetek: Let $G$ and $H$ be graphs and let $f \colon V(G)\rightarrow V(H)$ be a function. The Sierpiński product of $G$ and $H$ with respect to $f$, denoted by $G \otimes _f H$, is defined as the graph on the vertex set $V(G)\times V(H)$, consisting of $|V(G)|$ copies of $H$; for every edge $gg'$ of $G$ there is an edge between copies $gH$ and $g'H$ of $H$ associated with the vertices $g$ and $g'$ of $G$, respectively, of the form $(g,f(g'))(g',f(g))$. The Sierpiński metric dimension and the upper Sierpiński metric dimension of two graphs are determined. Closed formulas are determined for Sierpiński products of trees, and for Sierpiński products of two cycles where the second factor is a triangle. We also prove that the layers with respect to the second factor in a Sierpiński product graph are convex. Ključne besede: Sierpiński product of graphs, metric dimension, trees, convex subgraph Objavljeno v DiRROS: 16.02.2024; Ogledov: 382; Prenosov: 171 Celotno besedilo (432,07 KB) Gradivo ima več datotek! Več... |
24. Partial domination in supercubic graphsCsilla Bujtás, Michael A. Henning, Sandi Klavžar, 2024, izvirni znanstveni članek Povzetek: For some $\alpha$ with $0 < \alpha \le 1$, a subset $X$ of vertices in a graph $G$ of order $n$ is an $\alpha$-partial dominating set of $G$ if the set $X$ dominates at least $\alpha \times n$ vertices in $G$. The $\alpha$-partial domination number ${\rm pd}_{\alpha}(G)$ of $G$ is the minimum cardinality of an $\alpha$-partial dominating set of $G$. In this paper partial domination of graphs with minimum degree at least $3$ is studied. It is proved that if $G$ is a graph of order $n$ and with $\delta(G)\ge 3$, then ${\rm pd}_{\frac{7}{8}}(G) \le \frac{1}{3}n$. If in addition $n\ge 60$, then ${\rm pd}_{\frac{9}{10}}(G) \le \frac{1}{3}n$, and if $G$ is a connected cubic graph of order $n\ge 28$, then ${\rm pd}_{\frac{13}{14}}(G) \le \frac{1}{3}n$. Along the way it is shown that there are exactly four connected cubic graphs of order $14$ with domination number $5$. Ključne besede: domination, partial domination, cubic graphs, supercubic graphs Objavljeno v DiRROS: 15.02.2024; Ogledov: 364; Prenosov: 141 Celotno besedilo (304,87 KB) Gradivo ima več datotek! Več... |
25. From language models to large-scale food and biomedical knowledge graphsGjorgjina Cenikj, Lidija Strojnik, Risto Angelski, Nives Ogrinc, Barbara Koroušić-Seljak, Tome Eftimov, 2023, izvirni znanstveni članek Povzetek: Knowledge about the interactions between dietary and biomedical factors is scattered throughout uncountable research articles in an unstructured form (e.g., text, images, etc.) and requires automatic structuring so that it can be provided to medical professionals in a suitable format. Various biomedical knowledge graphs exist, however, they require further extension with relations between food and biomedical entities. In this study, we evaluate the performance of three state-of-the-art relation-mining pipelines (FooDis, FoodChem and ChemDis) which extract relations between food, chemical and disease entities from textual data. We perform two case studies, where relations were automatically extracted by the pipelines and validated by domain experts. The results show that the pipelines can extract relations with an average precision around 70%, making new discoveries available to domain experts with reduced human effort, since the domain experts should only evaluate the results, instead of finding, and reading all new scientific papers. Ključne besede: biomedical knowledge graphs, relation-mining pipelines, relation extraction, validation Objavljeno v DiRROS: 17.05.2023; Ogledov: 580; Prenosov: 241 Celotno besedilo (2,39 MB) Gradivo ima več datotek! Več... |