1. Variety of mutual-visibility problems in graphsSerafino Cicerone, Gabriele Di Stefano, Lara Drožđek, Jaka Hedžet, Sandi Klavžar, Ismael G. Yero, 2023, izvirni znanstveni članek Povzetek: If $X$ is a subset of vertices of a graph $G$, then vertices $u$ and $v$ are $X$-visible if there exists a shortest $u,v$-path $P$ such that $V(P)\cap X \subseteq \{u,v\}$. If each two vertices from $X$ are $X$-visible, then $X$ is a mutual-visibility set. The mutual-visibility number of $G$ is the cardinality of a largest mutual-visibility set of $G$ and has been already investigated. In this paper a variety of mutual-visibility problems is introduced based on which natural pairs of vertices are required to be $X$-visible. This yields the total, the dual, and the outer mutual-visibility numbers. We first show that these graph invariants are related to each other and to the classical mutual-visibility number, and then we prove that the three newly introduced mutual-visibility problems are computationally difficult. According to this result, we compute or bound their values for several graphs classes that include for instance grid graphs and tori. We conclude the study by presenting some inter-comparison between the values of such parameters, which is based on the computations we made for some specific families.
Ključne besede: mutual-visibility, total mutual-visibility, dual mutual-visibility number, outer mutual-visibility, grid graphs, torus graphs, computational complexity
Objavljeno v DiRROS: 10.04.2024; Ogledov: 80; Prenosov: 43
 Celotno besedilo (456,36 KB)
Gradivo ima več datotek! Več... |
2. Graphs with equal Grundy domination and independence numberGábor Bacsó, Boštjan Brešar, Kirsti Kuenzel, Douglas F. Rall, 2023, izvirni znanstveni članek Povzetek: The Grundy domination number, ${\gamma_{\rm gr}}(G)$, of a graph $G$ is the maximum length of a sequence $(v_1,v_2,\ldots, v_k)$ of vertices in $G$ such that for every $i\in \{2,\ldots, k\}$, the closed neighborhood $N[v_i]$ contains a vertex that does not belong to any closed neighborhood $N[v_j]$, where $jKljučne besede: Grundy domination, independence number, upper domination number, bipartite graphs
Objavljeno v DiRROS: 09.04.2024; Ogledov: 79; Prenosov: 42
Celotno besedilo (803,91 KB)
Gradivo ima več datotek! Več... |
3. 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: 62; Prenosov: 38
Celotno besedilo (393,09 KB)
Gradivo ima več datotek! Več... |
4. Orientable domination in product-like graphsSarah Anderson, Boštjan Brešar, Sandi Klavžar, Kirsti Kuenzel, Douglas F. Rall, 2023, izvirni znanstveni članek Povzetek: 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].
Ključne besede: digraph, domination, orientable domination number, packing, graph product, corona graph
Objavljeno v DiRROS: 20.03.2024; Ogledov: 109; Prenosov: 52
Celotno besedilo (366,61 KB)
Gradivo ima več datotek! Več... |
5. Bordering of symmetric matrices and an application to the minimum number of distinct eigenvalues for the join of graphsAida Abiad, Shaun M. Fallat, Mark Kempton, Rupert H. Levene, Polona Oblak, Helena Šmigoc, Michael Tait, Kevin N. Vander Meulen, 2023, izvirni znanstveni članek Ključne besede: inverse eigenvalue problem, minimum number of distinct eigenvalues, borderings, joins of graphs, paths, cycles, hypercubes
Objavljeno v DiRROS: 18.03.2024; Ogledov: 88; Prenosov: 48
Celotno besedilo (485,46 KB)
Gradivo ima več datotek! Več... |
6. Computational complexity aspects of super dominationCsilla Bujtás, Nima Ghanbari, Sandi Klavžar, 2023, izvirni znanstveni članek Povzetek: Let ▫$G$▫ be a graph. A dominating set ▫$D\subseteq V(G)$▫ is a super dominating set if for every vertex ▫$x\in V(G) \setminus D$▫ there exists ▫$y\in D$▫ such that ▫$N_G(y)\cap (V(G)\setminus D)) = \{x\}$▫. The cardinality of a smallest super dominating set of ▫$G$▫ is the super domination number of ▫$G$▫. An exact formula for the super domination number of a tree ▫$T$▫ is obtained, and it is demonstrated that a smallest super dominating set of ▫$T$▫ can be computed in linear time. It is proved that it is NP-complete to decide whether the super domination number of a graph ▫$G$▫ is at most a given integer if ▫$G$▫ is a bipartite graph of girth at least ▫$8$▫. The super domination number is determined for all ▫$k$▫-subdivisions of graphs. Interestingly, in half of the cases the exact value can be efficiently computed from the obtained formulas, while in the other cases the computation is hard. While obtaining these formulas, II-matching numbers are introduced and proved that they are computationally hard to determine.
Ključne besede: super domination number, trees, bipartite graphs, k-subdivision of a graph, computational complexity, matching, II-matching number
Objavljeno v DiRROS: 14.03.2024; Ogledov: 94; Prenosov: 55
Celotno besedilo (453,39 KB)
Gradivo ima več datotek! Več... |
7. On a continuation of quaternionic and octonionic logarithm along curves and the winding numberGraziano Gentili, Jasna Prezelj, Fabio Vlacci, 2024, izvirni znanstveni članek Povzetek: This paper deals with the problem of finding a continuous extension of the hypercomplex (quaternionic or octonionic) logarithm along (quaternionic or octonionic) paths which avoid the origin. The main difficulty depends upon this fact: while a branch of the complex logarithm can be defined in a small open neighbourhood of a strictly negative real point, no continuous branch of the hypercomplex logarithm can be defined in any open set which contains a strictly negative real point. To overcome this difficulty, we use the logarithmic manifold: in general, the existence of a lift of a path to this manifold is not guaranteed and, indeed, the problem of lifting a path to the logarithmic manifold is completely equivalent to the problem of finding a continuation of the hypercomplex logarithm along this path. The second part of the paper scrutinizes the existence of a notion of winding number (with respect to the origin) for hypercomplex loops that avoid the origin, even though it is known that the definition of winding number for such loops is not natural in ${\mathbb R}^n$ when $n$ is greater than $2$. The surprise is that, in the hypercomplex setting, the new definition of winding number introduced in this paper can be given and has full meaning for a large class of hypercomplex loops (untwisted loops with companion that avoid the origin). Finally an original but rather natural notion of homotopy for these hypercomplex loops (the $c$-homotopy) is presented and it is proved to be suitable to comply with the intrinsic geometrical meaning of the winding number for this class of loops, namely, two such hypercomplex loops are $c$-homotopic if, and only if, they have the same winding number.
Ključne besede: hypercomplex logarithm, continuation of the hypercomplex logarithm along paths, winding number
Objavljeno v DiRROS: 04.03.2024; Ogledov: 131; Prenosov: 54
Celotno besedilo (720,93 KB)
Gradivo ima več datotek! Več... |
8. General position polynomialsVesna Iršič, Sandi Klavžar, Gregor Rus, James Tuite, 2024, izvirni znanstveni članek Povzetek: A subset of vertices of a graph $G$ is a general position set if no triple of vertices from the set lie on a common shortest path in $G$. In this paper we introduce the general position polynomial as $\sum_{i \geq 0} a_i x^i$, where $a_i$ is the number of distinct general position sets of $G$ with cardinality $i$. The polynomial is considered for several well-known classes of graphs and graph operations. It is shown that the polynomial is not unimodal in general, not even on trees. On the other hand, several classes of graphs, including Kneser graphs $K(n,2)$, with unimodal general position polynomials are presented.
Ključne besede: general position set, general position number, general position polynomial, unimodality, trees, Cartesian product of graphs, Kneser graphs
Objavljeno v DiRROS: 28.02.2024; Ogledov: 119; Prenosov: 81
Celotno besedilo (384,07 KB)
Gradivo ima več datotek! Več... |
9. Packings in bipartite prisms and hypercubesBoštjan Brešar, Sandi Klavžar, Douglas F. Rall, 2024, izvirni znanstveni članek Povzetek: The $2$-packing number $\rho_2(G)$ of a graph $G$ is the cardinality of a largest $2$-packing of $G$ and the open packing number $\rho^{\rm o}(G)$ is the cardinality of a largest open packing of $G$, where an open packing (resp. $2$-packing) is a set of vertices in $G$ no two (closed) neighborhoods of which intersect. It is proved that if $G$ is bipartite, then $\rho^{\rm o}(G\Box K_2) = 2\rho_2(G)$. For hypercubes, the lower bounds $\rho_2(Q_n) \ge 2^{n - \lfloor \log n\rfloor -1}$ and $\rho^{\rm o}(Q_n) \ge 2^{n - \lfloor \log (n-1)\rfloor -1}$ are established. These findings are applied to injective colorings of hypercubes. In particular, it is demonstrated that $Q_9$ is the smallest hypercube which is not perfect injectively colorable. It is also proved that $\gamma_t(Q_{2^k}\times H) = 2^{2^k-k}\gamma_t(H)$, where $H$ is an arbitrary graph with no isolated vertices.
Ključne besede: 2-packing number, open packing number, bipartite prism, hypercube, injective coloring, total domination number
Objavljeno v DiRROS: 19.02.2024; Ogledov: 186; Prenosov: 68
Celotno besedilo (231,57 KB)
Gradivo ima več datotek! Več... |
10. Lower (total) mutual-visibility number in graphsBoštjan Brešar, Ismael G. Yero, 2024, izvirni znanstveni članek Povzetek: Given a graph $G$, a set $X$ of vertices in $G$ satisfying that between every two vertices in $X$ (respectively, in $G$) there is a shortest path whose internal vertices are not in $X$ is a mutual-visibility (respectively, total mutual-visibility) set in $G$. The cardinality of a largest (total) mutual-visibility set in $G$ is known under the name (total) mutual-visibility number, and has been studied in several recent works. In this paper, we propose two lower variants of these concepts, defined as the smallest possible cardinality among all maximal (total) mutual-visibility sets in $G$, and denote them by $\mu^{-}(G)$ and $\mu_t^{-}(G)$, respectively. While the total mutual-visibility number is never larger than the mutual-visibility number in a graph $G$, we prove that both differences $\mu^{-}(G)-\mu_t^{-}(G)$ and $\mu_t^{-}(G)-\mu^{-}(G)$ can be arbitrarily large. We characterize graphs $G$ with some small values of $\mu^{-}(G)$ and $\mu_t^{-}(G)$, and prove a useful tool called the Neighborhood Lemma, which enables us to find upper bounds on the lower mutual-visibility number in several classes of graphs. We compare the lower mutual-visibility number with the lower general position number, and find a close relationship with the Bollobás-Wessel theorem when this number is considered in Cartesian products of complete graphs. Finally, we also prove the NP-completeness of the decision problem related to $\mu_t^{-}(G)$.
Ključne besede: mutual-visibility set, mutual-visibility number, total mutual-visibility set, computational complexity
Objavljeno v DiRROS: 19.02.2024; Ogledov: 145; Prenosov: 64
Celotno besedilo (567,18 KB)
Gradivo ima več datotek! Več... |
