21. Resolvability and convexity properties in the Sierpiński product of graphsMichael A. Henning, Sandi Klavžar, Ismael G. Yero, 2024, original scientific article Abstract: 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.
Keywords: Sierpiński product of graphs, metric dimension, trees, convex subgraph
Published in DiRROS: 16.02.2024; Views: 179; Downloads: 78
 Full text (432,07 KB)
This document has many files! More... |
22. Partial domination in supercubic graphsCsilla Bujtás, Michael A. Henning, Sandi Klavžar, 2024, original scientific article Abstract: 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$.
Keywords: domination, partial domination, cubic graphs, supercubic graphs
Published in DiRROS: 15.02.2024; Views: 173; Downloads: 79
Full text (304,87 KB)
This document has many files! More... |
23. 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, original scientific article Abstract: 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.
Keywords: biomedical knowledge graphs, relation-mining pipelines, relation extraction, validation
Published in DiRROS: 17.05.2023; Views: 412; Downloads: 167
Full text (2,39 MB)
This document has many files! More... |
