Search the repository

A+ | A- | | SLO | ENG

Abstract: By suitably adjusting the tropical algebra technique we compute the rainbow independent domination numbers of several infinite families of graphs including Cartesian products $C_n \Box P_m$ and $C_n \Box C_m$ for all $n$ and $m\le 5$, and generalized Petersen graphs $P(n,2)$ for $n \ge 3$.
Keywords: graph theory, rainbow independent domination number, path algebra, tropical algebra
Published in DiRROS: 03.10.2024; Views: 154; Downloads: 60
Full text (459,61 KB)
This document has many files! More...

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: 135; Downloads: 77
Full text (283,48 KB)
This document has many files! More...

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: 137; Downloads: 74
Full text (503,82 KB)
This document has many files! More...

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: 129; Downloads: 60
Full text (504,15 KB)
This document has many files! More...

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: 151; Downloads: 77
Full text (618,95 KB)
This document has many files! More...