31. Covering the edges of a graph with trianglesCsilla Bujtás, Akbar Davoodi, Laihao Ding, Ervin Győri, Zsolt Tuza, Donglei Yang, 2025, original scientific article Abstract: In a graph $G$, let $\rho_\triangle(G)$ denote the minimum size of a set of edges and triangles that cover all edges of $G$, and let $\alpha_1(G)$ be the maximum size of an edge set that contains at most one edge from each triangle. Motivated by a question of Erdős, Gallai, and Tuza, we study the relationship between $\rho_\triangle(G)$ and $\alpha_1(G)$ and establish a sharp upper bound on $\rho_\triangle(G)$. We also prove Nordhaus-Gaddum-type inequalities for the considered invariants. Keywords: edge-disjoint triangles, edge clique covering, Nordhaus-Gaddum inequality Published in DiRROS: 03.10.2024; Views: 105; Downloads: 56
Full text (283,48 KB) This document has many files! More... |
32. Vertex-primitive digraphs with large fixityMarco Barbieri, Primož Potočnik, 2024, original scientific article Abstract: The relative fixity of a digraph $\Gamma$ is defined as the ratio between the largest number of vertices fixed by a nontrivial automorphism of $\Gamma$ and the number of vertices of $\Gamma$ .We characterize the vertex-primitive digraphs whose relative fixity is at least $1 \over 3$, and we show that there are only finitely many vertex-primitive digraphs of bounded out-valency and relative fixity exceeding a positive constant. Keywords: vertex-primitive digraphs, fixity, product action, graphs Published in DiRROS: 03.10.2024; Views: 154; Downloads: 47
Full text (397,05 KB) This document has many files! More... |
33. Fast winning strategies for Staller in the Maker-Breaker domination gameCsilla Bujtás, Pakanun Dokyeesun, 2024, original scientific article Abstract: The Maker-Breaker domination game is played on a graph $G$ by two players, called Dominator and Staller, who alternately choose a vertex that has not been played so far. Dominator wins the game if his moves form a dominating set. Staller wins if she plays all vertices from a closed neighborhood of a vertex $v \in V(G)$. Dominator's fast winning strategies were studied earlier. In this work, we concentrate on the cases when Staller has a winning strategy in the game. We introduce the invariant $\gamma'_{\rm SMB}(G)$ (resp., $\gamma_{\rm SMB}(G)$) which is the smallest integer $k$ such that, under any strategy of Dominator, Staller can win the game by playing at most $k$ vertices, if Staller (resp., Dominator) plays first on the graph $G$. We prove some basic properties of $\gamma_{\rm SMB}(G)$ and $\gamma'_{\rm SMB}(G)$ and study the parameters' changes under some operators as taking the disjoint union of graphs or deleting a cut vertex. We show that the inequality $\delta(G)+1 \le \gamma'_{\rm SMB}(G) \le \gamma_{\rm SMB}(G)$ always holds and that for every three integers $r,s,t$ with $2\le r\le s\le t$, there exists a graph $G$ such that $\delta(G)+1 = r$, $\gamma'_{\rm SMB}(G) = s$, and $\gamma_{\rm SMB}(G) = t$. We prove exact formulas for $\gamma'_{\rm SMB}(G)$ where $G$ is a path, or it is a tadpole graph which is obtained from the disjoint union of a cycle and a path by adding one edge between them. Keywords: domination game, Maker–Breaker game, winning number, Maker-Breaker domination game, closed neighborhood hypergraph Published in DiRROS: 03.10.2024; Views: 98; Downloads: 57
Full text (503,82 KB) This document has many files! More... |
34. Comparative simulative analysis and design of single-chain self-assembled protein cagesFei Xiao, Longfei Luo, Xin Liu, Ajasja Ljubetič, Nengzhi Jin, Roman Jerala, Guang Hu, 2024, original scientific article Abstract: Coiled-coil protein origami (CCPO) is a modular strategy for the de novo design of polypeptide nanostructures. It represents a type of modular design based on pairwise-interacting coiled-coil (CC) units with a single-chain protein programmed to fold into a polyhedral cage. However, the mechanisms underlying the self-assembly of the protein tetrahedron are still not fully understood. In the present study, 18 CCPO cages with three different topologies were modeled in silico. Then, molecular dynamics simulations and CC parameters were calculated to characterize the dynamic properties of protein tetrahedral cages at both the local and global levels. Furthermore, a deformed CC unit was redesigned, and the stability of the new cage was significantly improved. Keywords: chemical structure, conformation, genetics oligomers stability Published in DiRROS: 03.10.2024; Views: 118; Downloads: 32
Full text (2,23 MB) This document has many files! More... |
35. A note on the 2-colored rectilinear crossing number of random point sets in the unit squareSergio Cabello, Éva Czabarka, Ruy Fabila-Monroy, Yuya Higashikawa, Raimund Seidel, László Székely, Josef Tkadlec, Alexandra Wesolek, 2024, original scientific article Abstract: Let $S$ be a set of four points chosen independently, uniformly at random from a square. Join every pair of points of $S$ with a straight line segment. Color these edges red if they have positive slope and blue, otherwise. We show that the probability that $S$ defines a pair of crossing edges of the same color is equal to $1/4$. This is connected to a recent result of Aichholzer et al. who showed that by $2$-colouring the edges of a geometric graph and counting monochromatic crossings instead of crossings, the number of crossings can be more than halved. Our result shows that for the described random drawings, there is a coloring of the edges such that the number of monochromatic crossings is in expectation ${1 \over 2} - {7 \over 50}$ of the total number of crossings. Keywords: arrangement of points, flat, hyperplane Published in DiRROS: 03.10.2024; Views: 94; Downloads: 46
Full text (504,15 KB) This document has many files! More... |
36. Conservation of molecular responses upon viral infection in the non-vascular plant Marchantia polymorphaEric Ros-Moner, Tamara Jiménez-Góngora, Luis Villar-Martin, Lana Vogrinec, Víctor M. González-Miguel, Denis Kutnjak, Ignacio Rubio-Somoza, 2024, original scientific article Abstract: After plants transitioned from water to land around 450 million years ago, they faced novel pathogenic microbes. Their colonization of diverse habitats was driven by anatomical innovations like roots, stomata, and vascular tissue, which became central to plant-microbe interactions. However, the impact of these innovations on plant immunity and pathogen infection strategies remains poorly understood. Here, we explore plant-virus interactions in the bryophyte Marchantia polymorpha to gain insights into the evolution of these relationships. Virome analysis reveals that Marchantia is predominantly associated with RNA viruses. Comparative studies with tobacco mosaic virus (TMV) show that Marchantia shares core defense responses with vascular plants but also exhibits unique features, such as a sustained wound response preventing viral spread. Additionally, general defense responses in Marchantia are equivalent to those restricted to vascular tissues in Nicotiana, suggesting that evolutionary acquisition of developmental innovations results in re-routing of defense responses in vascular plants. Keywords: plant-virus interactions, bryophytes, virome analysis, high-throughput sequencing, virology, pathogenic, innovations, interactions, RNA viruses, plant defense response, botany Published in DiRROS: 02.10.2024; Views: 136; Downloads: 236
Full text (3,00 MB) This document has many files! More... |
37. Mutual-visibility in strong products of graphs via total mutual-visibilitySerafino Cicerone, Gabriele Di Stefano, Sandi Klavžar, Ismael G. Yero, 2024, original scientific article Abstract: Let $G$ be a graph and $X\subseteq V(G)$. Then $X$ is a mutual-visibility set if each pair of vertices from $X$ is connected by a geodesic with no internal vertex in $X$. The mutual-visibility number $\mu(G)$ of $G$ is the cardinality of a largest mutual-visibility set. In this paper, the mutual-visibility number of strong product graphs is investigated. As a tool for this, total mutual-visibility sets are introduced. Along the way, basic properties of such sets are presented. The (total) mutual-visibility number of strong products is bounded from below in two ways, and determined exactly for strong grids of arbitrary dimension. Strong prisms are studied separately and a couple of tight bounds for their mutual-visibility number are given. Keywords: mutual-visibility set, mutual-visibility number, total mutual-visibility set, strong product of graphs Published in DiRROS: 02.10.2024; Views: 129; Downloads: 66
Full text (618,95 KB) This document has many files! More... |
38. |
39. On distance magic labelings of Hamming graphs and folded hypercubesŠtefko Miklavič, Primož Šparl, 2024, original scientific article Abstract: Let $\Gamma = (V,E)$ be a graph of order $n$. A distance magic labeling of $\Gamma$ is a bijection $\ell \colon V \to \{1,2, \ldots, n\}$ for which there exists a positive integer $k$ such that $\sum_{x \in N(u)} \ell(x) = k$ for all vertices $u \in V$, where $N(u)$ is the neighborhood of $u$. A graph is said to be distance magic if it admits a distance magic labeling. The Hamming graph $\mathrm{H}(D,q)$, where $D, q$ are positive integers, is the graph whose vertex set consists of all words of length $D$ over an alphabet of size $q$ in which two vertices are adjacent whenever the corresponding words differ in precisely one position. The well-known hypercubes are precisely the Hamming graphs with $q = 2$. Distance magic hypercubes were classified in two papers from 2013 and 2016. In this paper we consider all Hamming graphs. We provide a sufficient condition for a Hamming graph to be distance magic and as a corollary provide an infinite number of pairs $(D, q)$ for which the corresponding Hamming graph $\mathrm{H}(D,q)$ is distance magic. A folded hypercube is a graph obtained from a hypercube by identifying pairs of vertices at maximal distance. We classify distance magic folded hypercubes by showing that the dimension-$D$ folded hypercube is distance magic if and only if $D$ is divisible by $4$. Keywords: distance magic labeling, distance magic graph, Hamming graph, folded hypercube Published in DiRROS: 02.10.2024; Views: 103; Downloads: 49
Full text (484,67 KB) This document has many files! More... |
40. Testing woodchips for their efficiency in stimulating aquatic nutrient uptake at different experimental and spatial scalesElmira Akbari, Tjaša Matjašič, Anna-Lisa Dittrich, Katrin Attermeyer, Rebecca Hood-Nowotny, Gabriele Weigelhofer, 2024, original scientific article Abstract: Introduction: Woodchips as a source of particulate organic carbon (POC) are proposed as a nature-based solution to enhance nutrient uptake and retention in agricultural streams. However, the effective implementation of woodchips for nutrient removal in streams requires an advanced understanding of their potential and limits, considering their performance under various environmental conditions. This study tested the efficiency of woodchips on the uptake of soluble reactive phosphorus (SRP) and ammonium (N-NH4) across different experimental scales and complexity. We investigated whether the presence of woodchips can increase SRP and N-NH4 uptake in laboratory flumes under controlled conditions, outdoor flumes under semi-controlled conditions, and agricultural streams. Additionally, we examined how the effects of woodchips will change over time via a 6-week incubation in the outdoor flumes. Methods: The woodchips were pre-colonized for four weeks to allow the growth of biofilms. We performed short-term nutrient additions without (control) and with (treatment) woodchips in all three experimental setups. Uptake parameters were determined via concentration changes over time in the laboratory flumes and concentration changes over travel distance in the outdoor flumes and the stream channels. The effects of woodchips on SRP and N-NH4 uptake rates were analyzed using an effect size model. Results: We found positive effects of woodchips on nutrient uptake only in the laboratory flumes but no or even negative effects in the outdoor flumes and the agricultural streams. Over the 6-week incubation in the outdoor flumes, we did not observe significant changes in the effects of woodchips on nutrient uptake. Discussion: These findings highlight that considering experimental scales and influencing environmental conditions is crucial when testing the application of woodchips as nature-based solutions to mitigate nutrient loads in agricultural streams. Keywords: biofilms, nutrient uptake, particulate organic carbon (POC), soluble reactive phosphorus (SRP), ammonium (N-NH4), woodchips, experimental scales Published in DiRROS: 02.10.2024; Views: 100; Downloads: 217
Full text (2,53 MB) This document has many files! More... |