1901. Injective coloring of graphs revisitedBoštjan Brešar, Babak Samadi, Ismael G. Yero, 2023, izvirni znanstveni članek Povzetek: 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. Ključne besede: two-step graph of a graph, injective coloring, open packing, hypercubes Objavljeno v DiRROS: 09.04.2024; Ogledov: 462; Prenosov: 188 Celotno besedilo (460,72 KB) Gradivo ima več datotek! Več... |
1902. The core of a vertex-transitive complementary prismMarko Orel, 2023, izvirni znanstveni članek Povzetek: 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. Ključne besede: graph homomorphism, complementary prism, self-complementary graph, vertex-transitive graph, core Objavljeno v DiRROS: 09.04.2024; Ogledov: 454; Prenosov: 153 Celotno besedilo (309,75 KB) Gradivo ima več datotek! Več... |
1903. Domination and independence numbers of large 2-crossing-critical graphsVesna Iršič, Maruša Lekše, Miha Pačnik, Petra Podlogar, Martin Praček, 2023, izvirni znanstveni članek Povzetek: After 2-crossing-critical graphs were characterized in 2016, their most general subfamily, large 3-connected 2-crossing-critical graphs, has attracted separate attention. This paper presents sharp upper and lower bounds for their domination and independence number. Ključne besede: crossing-critical graphs, domination number, independence number Objavljeno v DiRROS: 09.04.2024; Ogledov: 436; Prenosov: 193 Celotno besedilo (393,09 KB) Gradivo ima več datotek! Več... |
1904. |
1905. Sliding wear behaviour of conventional and cryotreated PM Cr-V (Vanadis 6) ledeburitic tool steelVenu Yarasu, Peter Jurči, Peter Gogola, Bojan Podgornik, Marko Sedlaček, 2023, izvirni znanstveni članek Ključne besede: cold work tool steel, conventional treatment, cryogenic treatment, hardness, reciprocal sliding, wear Objavljeno v DiRROS: 08.04.2024; Ogledov: 554; Prenosov: 77 Celotno besedilo (7,85 MB) Gradivo ima več datotek! Več... |
1906. Maximum matchings in geometric intersection graphsÉdouard Bonnet, Sergio Cabello, Wolfgang Mulzer, 2023, izvirni znanstveni članek Povzetek: Let $G$ be an intersection graph of $n$ geometric objects in the plane. We show that a maximum matching in $G$ can be found in $O(\rho^{3\omega/2}n^{\omega/2})$ time with high probability, where $\rho$ is the density of the geometric objects and $\omega>2$ is a constant such that $n \times n$ matrices can be multiplied in $O(n^\omega)$ time. The same result holds for any subgraph of $G$, as long as a geometric representation is at hand. For this, we combine algebraic methods, namely computing the rank of a matrix via Gaussian elimination, with the fact that geometric intersection graphs have small separators. We also show that in many interesting cases, the maximum matching problem in a general geometric intersection graph can be reduced to the case of bounded density. In particular, a maximum matching in the intersection graph of any family of translates of a convex object in the plane can be found in $O(n^{\omega/2})$ time with high probability, and a maximum matching in the intersection graph of a family of planar disks with radii in $[1, \Psi]$ can be found in $O(\Psi^6\log^{11} n + \Psi^{12 \omega} n^{\omega/2})$ time with high probability. Ključne besede: computational geometry, geometric intersection graphs, disk graphs, unit-disk graphs, matchings Objavljeno v DiRROS: 08.04.2024; Ogledov: 441; Prenosov: 207 Celotno besedilo (576,69 KB) Gradivo ima več datotek! Več... |
1907. Maker-Breaker domination game on trees when Staller winsCsilla Bujtás, Pakanun Dokyeesun, Sandi Klavžar, 2023, izvirni znanstveni članek Povzetek: In the Maker-Breaker domination game played on a graph $G$, Dominator's goal is to select a dominating set and Staller's goal is to claim a closed neighborhood of some vertex. We study the cases when Staller can win the game. If Dominator (resp., Staller) starts the game, then $\gamma_{\rm SMB}(G)$ (resp., $\gamma_{\rm SMB}'(G)$) denotes the minimum number of moves Staller needs to win. For every positive integer $k$, trees $T$ with $\gamma_{\rm SMB}'(T)=k$ are characterized and a general upper bound on $\gamma_{\rm SMB}'$ is proved. Let $S = S(n_1,\dots, n_\ell)$ be the subdivided star obtained from the star with $\ell$ edges by subdividing its edges $n_1-1, \ldots, n_\ell-1$ times, respectively. Then $\gamma_{\rm SMB}'(S)$ is determined in all the cases except when $\ell\ge 4$ and each $n_i$ is even. The simplest formula is obtained when there are at least two odd $n_i$s. If ▫$n_1$▫ and $n_2$ are the two smallest such numbers, then $\gamma_{\rm SMB}'(S(n_1,\dots, n_\ell))=\lceil \log_2(n_1+n_2+1)\rceil$▫. For caterpillars, exact formulas for $\gamma_{\rm SMB}$ and for $\gamma_{\rm SMB}'$ are established. Ključne besede: domination game, Maker-Breaker game, Maker-Breaker domination game, hypergraphs, trees, subdivided stars, caterpillars Objavljeno v DiRROS: 08.04.2024; Ogledov: 584; Prenosov: 238 Celotno besedilo (255,58 KB) Gradivo ima več datotek! Več... |
1908. The Calabi-Yau problem for minimal surfaces with Cantor endsFranc Forstnerič, 2023, izvirni znanstveni članek Povzetek: We show that every connected compact or bordered Riemann surface contains a Cantor set whose complement admits a complete conformal minimal immersion in ${\mathbb R}^3$ with bounded image. The analogous result holds for holomorphic immersions into any complex manifold of dimension at least $2$, for holomorphic null immersions into ${\mathbb C}^n$ with $n \ge 3$, for holomorphic Legendrian immersions into an arbitrary complex contact manifold, and for superminimal immersions into any selfdual or anti-self-dual Einstein four-manifold. Ključne besede: minimal surfaces, Calabi–Yau problem, null curve, Legendrian curve Objavljeno v DiRROS: 08.04.2024; Ogledov: 414; Prenosov: 179 Celotno besedilo (516,47 KB) Gradivo ima več datotek! Več... |
1909. Generalized Pell graphsVesna Iršič, Sandi Klavžar, Elif Tan, 2023, izvirni znanstveni članek Povzetek: 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. Ključne besede: Fibonacci cubes, Pell graphs, generating functions, center of graph, median graphs, k-Fibonacci sequence Objavljeno v DiRROS: 08.04.2024; Ogledov: 468; Prenosov: 198 Celotno besedilo (345,71 KB) Gradivo ima več datotek! Več... |
1910. |