1. Mutual-visibility problems on graphs of diameter twoSerafino Cicerone, Gabriele Di Stefano, Sandi Klavžar, Ismael G. Yero, 2024, izvirni znanstveni članek Povzetek: The mutual-visibility problem in a graph $G$ asks for the cardinality of a largest set of vertices $S\subseteq V(G)$ so that for any two vertices $x,y \in S$ there is a shortest $x,y$-path $P$ so that all internal vertices of $P$ are not in $S$. This is also said as $x,y$ are visible with respect to $S$, or $S$-visible for short. Variations of this problem are known, based on the extension of the visibility property of vertices that are in and/or outside $S$. Such variations are called total, outer and dual mutual-visibility problems. This work is focused on studying the corresponding four visibility parameters in graphs of diameter two, throughout showing bounds and/or closed formulae for these parameters. The mutual-visibility problem in the Cartesian product of two complete graphs is equivalent to (an instance of) the celebrated Zarankiewicz's problem. Here we study the dual and outer mutual-visibility problem for the Cartesian product of two complete graphs and all the mutual-visibility problems for the direct product of such graphs as well. We also study all the mutual-visibility problems for the line graphs of complete and complete bipartite graphs. As a consequence of this study, we present several relationships between the mentioned problems and some instances of the classical Turán problem. Moreover, we study the visibility problems for cographs and several non-trivial diameter-two graphs of minimum size.
Ključne besede: mutual-visibility set, mutual-visibility number, diameter-two graphs, line graphs, cographs
Objavljeno v DiRROS: 27.05.2024; Ogledov: 36; Prenosov: 29
 Celotno besedilo (558,13 KB)
Gradivo ima več datotek! Več... |
2. |
3. 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: 138; Prenosov: 76
Celotno besedilo (456,36 KB)
Gradivo ima več datotek! Več... |
4. 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: 137; Prenosov: 74
Celotno besedilo (803,91 KB)
Gradivo ima več datotek! Več... |
5. 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: 138; Prenosov: 65
Celotno besedilo (393,09 KB)
Gradivo ima več datotek! Več... |
6. 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: 152; Prenosov: 55
Celotno besedilo (576,69 KB)
Gradivo ima več datotek! Več... |
7. 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: 174; Prenosov: 65
Celotno besedilo (345,71 KB)
Gradivo ima več datotek! Več... |
8. |
9. The Sierpiński product of graphsJurij Kovič, Tomaž Pisanski, Sara Sabrina Zemljič, Arjana Žitnik, 2023, izvirni znanstveni članek Povzetek: 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.
Ključne besede: Sierpiński graphs, graph products, connectivity, planarity, symmetry
Objavljeno v DiRROS: 19.03.2024; Ogledov: 299; Prenosov: 265
Celotno besedilo (533,30 KB)
Gradivo ima več datotek! Več... |
10. Distance formula for direct-co-direct product in the case of disconnected factorsAleksander Kelenc, Iztok Peterin, 2023, izvirni znanstveni članek Povzetek: Direct-co-direct product $G\circledast H$ of graphs $G$ and $H$ is a graph on the vertex set $V(G)\times V(H)$. Two vertices $(g,h)$ and $(g',h')$ are adjacent if $gg'\in E(G)$ and $hh'\in E(H)$ or $gg'\notin E(G)$ and $hh'\notin E(H)$. We show that if at most one factor of $G\circledast H$ is connected, then the distance between two vertices of $G\circledast H$ is bounded by three unless some small number of exceptions. All the exceptions are completely described which yields the distance formula.
Ključne besede: direct-co-direct product, distance, eccentricity, disconnected graphs
Objavljeno v DiRROS: 19.03.2024; Ogledov: 150; Prenosov: 74
Celotno besedilo (450,88 KB)
Gradivo ima več datotek! Več... |
