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, original scientific article Abstract: 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.
Keywords: mutual-visibility, total mutual-visibility, dual mutual-visibility number, outer mutual-visibility, grid graphs, torus graphs, computational complexity
Published in DiRROS: 10.04.2024; Views: 79; Downloads: 42
 Full text (456,36 KB)
This document has many files! More... |
2. Graphs with equal Grundy domination and independence numberGábor Bacsó, Boštjan Brešar, Kirsti Kuenzel, Douglas F. Rall, 2023, original scientific article Abstract: 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 $jKeywords: Grundy domination, independence number, upper domination number, bipartite graphs
Published in DiRROS: 09.04.2024; Views: 73; Downloads: 42
Full text (803,91 KB)
This document has many files! More... |
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, original scientific article Abstract: 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.
Keywords: crossing-critical graphs, domination number, independence number
Published in DiRROS: 09.04.2024; Views: 60; Downloads: 36
Full text (393,09 KB)
This document has many files! More... |
4. Maximum matchings in geometric intersection graphsÉdouard Bonnet, Sergio Cabello, Wolfgang Mulzer, 2023, original scientific article Abstract: 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.
Keywords: computational geometry, geometric intersection graphs, disk graphs, unit-disk graphs, matchings
Published in DiRROS: 08.04.2024; Views: 80; Downloads: 34
Full text (576,69 KB)
This document has many files! More... |
5. Generalized Pell graphsVesna Iršič, Sandi Klavžar, Elif Tan, 2023, original scientific article Abstract: 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.
Keywords: Fibonacci cubes, Pell graphs, generating functions, center of graph, median graphs, k-Fibonacci sequence
Published in DiRROS: 08.04.2024; Views: 84; Downloads: 35
Full text (345,71 KB)
This document has many files! More... |
6. |
7. The Sierpiński product of graphsJurij Kovič, Tomaž Pisanski, Sara Sabrina Zemljič, Arjana Žitnik, 2023, original scientific article Abstract: 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.
Keywords: Sierpiński graphs, graph products, connectivity, planarity, symmetry
Published in DiRROS: 19.03.2024; Views: 127; Downloads: 48
Full text (533,30 KB)
This document has many files! More... |
8. Distance formula for direct-co-direct product in the case of disconnected factorsAleksander Kelenc, Iztok Peterin, 2023, original scientific article Abstract: 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.
Keywords: direct-co-direct product, distance, eccentricity, disconnected graphs
Published in DiRROS: 19.03.2024; Views: 79; Downloads: 44
Full text (450,88 KB)
This document has many files! More... |
9. A method for computing the edge-Hosoya polynomial with application to phenylenesMartin Knor, Niko Tratnik, 2023, original scientific article Abstract: The edge-Hosoya polynomial of a graph is the edge version of the famous Hosoya polynomial. Therefore, the edge-Hosoya polynomial counts the number of (unordered) pairs of edges at distance $k \ge 0$ in a given graph. It is well known that this polynomial is closely related to the edge-Wiener index and the edge-hyper-Wiener index. As the main result of this paper, we greatly generalize an earlier result by providing a method for calculating the edge-Hosoya polynomial of a graph $G$ which is obtained by identifying two edges of connected bipartite graphs $G_1$ and $G_2$. To show how the main theorem can be used, we apply it to phenylene chains. In particular, we present the recurrence relations and a linear time algorithm for calculating the edge-Hosoya polynomial of any phenylene chain. As a consequence, closed formula for the edge-Hosoya polynomial of linear phenylene chains is derived.
Keywords: edge-Hosoya polynomial, graphs, phenylenes
Published in DiRROS: 18.03.2024; Views: 86; Downloads: 28
Full text (530,53 KB) |
10. Resonance graphs and a binary coding of perfect matchings of outerplane bipartite graphsSimon Brezovnik, Niko Tratnik, Petra Žigert Pleteršek, 2023, original scientific article Abstract: The aim of this paper is to investigate resonance graphs of $2$-connected outerplane bipartite graphs, which include various families of molecular graphs. Firstly, we present an algorithm for a binary coding of perfect matchings of these graphs. Further, $2$-connected outerplane bipartite graphs with isomorphic resonance graphs are considered. In particular, it is shown that if two $2$-connected outerplane bipartite graphs are evenly homeomorphic, then its resonance graphs are isomorphic. Moreover, we prove that for any $2$-connected outerplane bipartite graph $G$ there exists a catacondensed even ring systems $H$ such that the resonance graphs of $G$ and $H$ are isomorphic. We conclude with the characterization of $2$-connected outerplane bipartite graphs whose resonance graphs are daisy cubes.
Keywords: graph theory, resonance graphs, bipartite graphs
Published in DiRROS: 18.03.2024; Views: 77; Downloads: 31
Full text (433,15 KB) |
