Digitalni repozitorij raziskovalnih organizacij Slovenije

Iskanje po repozitoriju
A+ | A- | Pomoč | SLO | ENG

Iskalni niz: išči po
išči po
išči po
išči po

Možnosti:
  Ponastavi


Iskalni niz: "avtor" (Gabriele Di Stefano) .

1 - 2 / 2
Na začetekNa prejšnjo stran1Na naslednjo stranNa konec
1.
Mutual-visibility problems on graphs of diameter two
Serafino 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: 47; Prenosov: 32
.pdf Celotno besedilo (558,13 KB)
Gradivo ima več datotek! Več...

2.
Variety of mutual-visibility problems in graphs
Serafino 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
.pdf Celotno besedilo (456,36 KB)
Gradivo ima več datotek! Več...
Iskanje izvedeno v 0.11 sek.
Na vrh