1. Stress knowledge map : a knowledge graph resource for systems biology analysis of plant stress responsesCarissa Bleker, Živa Ramšak, Andras Bittner, Vid Podpečan, Maja Zagorščak, Bernhard Wurzinger, Špela Baebler, Marko Petek, Maja Križnik, Anže Županič, Kristina Gruden, 2024, original scientific article Abstract: Stress Knowledge Map (SKM; https://skm.nib.si) is a publicly available resource containing two complementary knowledge graphs that describe the current knowledge of biochemical, signaling, and regulatory molecular interactions in plants: a highly curated model of plant stress signaling (PSS; 543 reactions) and a large comprehensive knowledge network (488 390 interactions). Both were constructed by domain experts through systematic curation of diverse literature and database resources. SKM provides a single entry point for investigations of plant stress response and related growth trade-offs, as well as interactive explorations of current knowledge. PSS is also formulated as a qualitative and quantitative model for systems biology and thus represents a starting point for a plant digital twin. Here, we describe the features of SKM and show, through two case studies, how it can be used for complex analyses, including systematic hypothesis generation and design of validation experiments, or to gain new insights into experimental observations in plant biology. Keywords: Stress knowledge map, knowledge graph, knowledge network, entry point, plant digital twin, plant stress responses, plant signaling, systems biology Published in DiRROS: 11.06.2024; Views: 254; Downloads: 130
Full text (1,35 MB) This document has many files! More... |
2. Injective coloring of graphs revisitedBoštjan Brešar, Babak Samadi, Ismael G. Yero, 2023, original scientific article Abstract: An open packing in a graph $G$ is a set $S$ of vertices in $G$ such that no two vertices in $S$ have a common neighbor in $G$. The injective chromatic number $\chi_i(G)$ of $G$ is the smallest number of colors assigned to vertices of ▫$G$▫ such that each color class is an open packing. Alternatively, the injective chromatic number of $G$ is the chromatic number of the two-step graph of $G$, which is the graph with the same vertex set as $G$ in which two vertices are adjacent if they have a common neighbor. The concept of injective coloring has been studied by many authors, while in the present paper we approach it from two novel perspectives, related to open packings and the two-step graph operation. We prove several general bounds on the injective chromatic number expressed in terms of the open packing number. In particular, we prove that $\chi_i(G) \ge \frac{1}{2}\sqrt{\frac{1}{4}+\frac{2m-n}{\rho^{o}}}$ holds for any connected graph $G$ of order $n\ge 2$, size $m$, and the open packing number ${\rho^{o}}$, and characterize the class of graphs attaining the bound. Regarding the well known bound $\chi_i(G)\ge \Delta(G)$, we describe the family of extremal graphs and prove that deciding when the equality holds (even for regular graphs) is NP-complete, solving an open problem from an earlier paper. Next, we consider the chromatic number of the two-step graph of a graph, and compare it with the clique number and the maximum degree of the graph. We present two large families of graphs in which $\chi_i(G)$ equals the cardinality of a largest clique of the two-step graph of $G$. Finally, we consider classes of graphs that admit an injective coloring in which all color classes are maximal open packings. We give characterizations of three subclasses of these graphs among graphs with diameter 2, and find a partial characterization of hypercubes with this property. Keywords: two-step graph of a graph, injective coloring, open packing, hypercubes Published in DiRROS: 09.04.2024; Views: 316; Downloads: 131
Full text (460,72 KB) This document has many files! More... |
3. The core of a vertex-transitive complementary prismMarko Orel, 2023, original scientific article Abstract: The complementary prism $\Gamma \overline{\Gamma}$ is obtained from the union of a graph $\Gamma$ and its complement $\overline{\Gamma}$ where each pair of identical vertices in $\Gamma$ and $\overline{\Gamma}$ is joined by an edge. It generalizes the Petersen graph, which is the complementary prism of the pentagon. The core of a vertex-transitive complementary prism is studied. In particular, it is shown that a vertex-transitive complementary prism $\Gamma \overline{\Gamma}$ is a core, i.e. all its endomorphisms are automorphisms, whenever $\Gamma$ is a core or its core is a complete graph. Keywords: graph homomorphism, complementary prism, self-complementary graph, vertex-transitive graph, core Published in DiRROS: 09.04.2024; Views: 295; Downloads: 106
Full text (309,75 KB) This document has many files! More... |
4. Generalized Pell graphsVesna Iršič, Sandi Klavžar, Elif Tan, 2023, original scientific article Abstract: In this paper, generalized Pell graphs $\Pi_{n,k}$, $k\ge 2$, are introduced. The special case of $k=2$ are the Pell graphs $\Pi_{n}$ defined earlier by Munarini. Several metric, enumerative, and structural properties of these graphs are established. The generating function of the number of edges of $\Pi_{n,k}$ and the generating function of its cube polynomial are determined. The center of $\Pi_{n,k}$ is explicitly described; if $k$ is even, then it induces the Fibonacci cube $\Gamma_{n}$. It is also shown that $\Pi_{n,k}$ is a median graph, and that $\Pi_{n,k}$ embeds into a Fibonacci cube. Keywords: Fibonacci cubes, Pell graphs, generating functions, center of graph, median graphs, k-Fibonacci sequence Published in DiRROS: 08.04.2024; Views: 327; Downloads: 127
Full text (345,71 KB) This document has many files! More... |
5. Generalized cut method for computing Szeged-like polynomials with applications to polyphenyls and carbon nanoconesSimon Brezovnik, Niko Tratnik, 2023, original scientific article Abstract: Szeged, Padmakar-Ivan (PI), and Mostar indices are some of the most investigated distance-based Szeged-like topological indices. On the other hand, the polynomials related to these topological indices were also introduced, for example the Szeged polynomial, the edge- Szeged polynomial, the PI polynomial, the Mostar polynomial, etc. In this paper, we introduce a concept of the general Szeged-like polynomial for a connected strength-weighted graph. It turns out that this concept includes all the above mentioned polynomials and also infinitely many other graph polynomials. As the main result of the paper, we prove a cut method which enables us to efficiently calculate a Szeged-like polynomial by using the corresponding polynomials of strength-weighted quotient graphs obtained by a partition of the edge set that is coarser than ▫$\Theta^*$▫-partition. To the best of our knowledge, this represents the first implementation of the famous cut method to graph polynomials. Finally, we show how the deduced cut method can be applied to calculate some Szeged-like polynomials and corresponding topological indices of para-polyphenyl chains and carbon nanocones. Keywords: graph theory, carbon nanocone, topological indices Published in DiRROS: 20.03.2024; Views: 287; Downloads: 103
Full text (599,00 KB) |
6. Orientable domination in product-like graphsSarah Anderson, Boštjan Brešar, Sandi Klavžar, Kirsti Kuenzel, Douglas F. Rall, 2023, original scientific article Abstract: The orientable domination number, ${\rm DOM}(G)$, of a graph $G$ is the largest domination number over all orientations of $G$. In this paper, ${\rm DOM}$ is studied on different product graphs and related graph operations. The orientable domination number of arbitrary corona products is determined, while sharp lower and upper bounds are proved for Cartesian and lexicographic products. A result of Chartrand et al. from 1996 is extended by establishing the values of ${\rm DOM}(K_{n_1,n_2,n_3})$ for arbitrary positive integers $n_1,n_2$ and $n_3$. While considering the orientable domination number of lexicographic product graphs, we answer in the negative a question concerning domination and packing numbers in acyclic digraphs posed in [Domination in digraphs and their direct and Cartesian products, J. Graph Theory 99 (2022) 359-377]. Keywords: digraph, domination, orientable domination number, packing, graph product, corona graph Published in DiRROS: 20.03.2024; Views: 323; Downloads: 119
Full text (366,61 KB) This document has many files! More... |
7. The Sierpiński product of graphsJurij Kovič, Tomaž Pisanski, Sara Sabrina Zemljič, Arjana Žitnik, 2023, original scientific article Abstract: In this paper we introduce a product-like operation that generalizes the construction of the generalized Sierpiński graphs. Let $G$, $H$ be graphs and let $f: V(G) \to V(H)$ be a function. Then the Sierpiński product of graphs $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 $\{g, g'\}$ of $G$ there is an edge between copies $gH$ and $g'H$ of form $\{(g, f(g'), (g', f(g))\}$. Some basic properties of the Sierpiński product are presented. In particular, we show that the graph $G\otimes_f H$ is connected if and only if both graphs $G$ and $H$ are connected and we present some conditions that $G, \, H$ must fulfill for $G\otimes_f H$ to be planar. As for symmetry properties, we show which automorphisms of $G$ and $H$ extend to automorphisms of $G\otimes_f H$. In several cases we can also describe the whole automorphism group of the graph $G\otimes_f H$. Finally, we show how to extend the Sierpiński product to multiple factors in a natural way. By applying this operation $n$ times to the same graph we obtain an alternative approach to the well-known $n$-th generalized Sierpiński graph. Keywords: Sierpiński graphs, graph products, connectivity, planarity, symmetry Published in DiRROS: 19.03.2024; Views: 443; Downloads: 334
Full text (533,30 KB) This document has many files! More... |
8. The core of a vertex transitive complementary prism of a lexicographic productMarko Orel, 2023, original scientific article Abstract: The complementary prism of a graph $\Gamma$ is the graph $\Gamma \overline{\Gamma}$, which is formed from the union of $\Gamma$ and its complement $\overline{\Gamma}$ by adding an edge between each pair of identical vertices in $\Gamma$ and $\overline{\Gamma}$. Vertex-transitive self-complementary graphs provide vertex-transitive complementary prisms. It was recently proved by the author that $\Gamma \overline{\Gamma}$ is a core, i.e. all its endomorphisms are automorphisms, whenever $\Gamma$ is vertex-transitive, self-complementary, and either $\Gamma$ is a core or its core is a complete graph. In this paper the same conclusion is obtained for some other classes of vertex-transitive self-complementary graphs that can be decomposed as a lexicographic product $\Gamma = \Gamma_1 [\Gamma_2]$. In the process some new results aboutthe homomorphisms of a lexicographic product are obtained. Keywords: graph homomorphism, core, complementary prism, self-complementary graph, vertex-transitive graph, lexicographic product Published in DiRROS: 19.03.2024; Views: 256; Downloads: 137
Full text (411,68 KB) This document has many files! More... |
9. How to compute the M-polynomial of (chemical) graphsEmeric Deutsch, Sandi Klavžar, Gašper Domen Romih, 2023, original scientific article Abstract: Let $G$ be a graph and let $m_{i,j}(G)$, $i,j\ge 1$, be the number of edges $uv$ of ▫$G$▫ such that $\{d_v(G), d_u(G)\} = \{i,j\}$. The M-polynomial of $G$ is $M(G;x,y) = \sum_{i\le j} m_{i,j}(G)x^iy^j$. A general method for calculating the M-polynomials for arbitrary graph families is presented. The method is further developed for the case where the vertices of a graph have degrees 2 and $p$, where $p\ge 3$, and further for such planar graphs. The method is illustrated on families of chemical graphs. Keywords: M-polynomial, chemical graph, planar graph Published in DiRROS: 18.03.2024; Views: 290; Downloads: 86
Full text (376,13 KB) |
10. Resonance graphs and a binary coding of perfect matchings of outerplane bipartite graphsSimon Brezovnik, Niko Tratnik, Petra Žigert Pleteršek, 2023, original scientific article Abstract: The aim of this paper is to investigate resonance graphs of $2$-connected outerplane bipartite graphs, which include various families of molecular graphs. Firstly, we present an algorithm for a binary coding of perfect matchings of these graphs. Further, $2$-connected outerplane bipartite graphs with isomorphic resonance graphs are considered. In particular, it is shown that if two $2$-connected outerplane bipartite graphs are evenly homeomorphic, then its resonance graphs are isomorphic. Moreover, we prove that for any $2$-connected outerplane bipartite graph $G$ there exists a catacondensed even ring systems $H$ such that the resonance graphs of $G$ and $H$ are isomorphic. We conclude with the characterization of $2$-connected outerplane bipartite graphs whose resonance graphs are daisy cubes. Keywords: graph theory, resonance graphs, bipartite graphs Published in DiRROS: 18.03.2024; Views: 300; Downloads: 82
Full text (433,15 KB) |