20.500.12556/RUL-167519 Vzajemna vidnost in celotna vzajemna vidnost v grafih Mutual-visibility and total mutual-visibility in graphs Naj bo $G=(V(G),E(G))$ graf in $X \subseteq V(G)$. Pravimo, da je množica $X$ vzajemno vidna, če za par vozlišč $u,v \in X$ velja, da na najkrajši poti med njima ne leži nobeno drugo vozlišče iz $X$. Vzajemna vidnost grafa $G$ je kardinalna vrednost katerekoli največje vzajemno vidne množice, $\mu(G)=|X|$. Naj bo še $X_t \subseteq V(G)$. Množica $X_t$ je celotno vzajemno vidna, če med poljubnima vozliščema iz $V(G)$ obstaja najkrajša pot, na kateri ne leži vozlišče iz $X_t$. Kardinalnost katerekoli največje celotno vzajemno vidne množice $X_t$ imenujemo celotna vzajemna vidnost grafa $G$, ki jo označimo z $\mu_t(G)=|X_t|$. S pomočjo različnih grafovskih invariant so podane spodnje in zgornje meje za $\mu(G)$ in $\mu_t(G)$. Za nekatere družine grafov in njihove produkte so podane točne vrednosti. Dokazano je, da je problem NP-poln. Let $G=(V(G),E(G))$ be a graph and a set of $X \subseteq V(G)$. $X$ is a mutual-visibility set if there exists a shortest path between vertices of $X$ without further vertices from $X$. Mutual-visibility of a graph $G$ is the cardinality of any largest mutually visible set, $\mu(G)=|X|$. Let $X_t \subseteq V(G)$ be a set. $X_t$ is total mutual-visibility set if there exists a shortest path between any two vertices of $V(G)$ without further vertices from $X_t$. The cardinality of any largest total mutual visibility set $X_t$ is called the total mutual-visibility number of the graph $G$, denoted as $\mu_t(G)=|X_t|$. Lower and upper bounds for $\mu(G)$ and $\mu_t(G)$ are given using various graph invariants. Exact values are given for certain graph families and their products. It is proven that the problem is NP-complete. graf vzajemna vidnost leksikografski produkt grafov kartezični produkt grafov graph mutual-visibility lexicographic product of graphs Cartesian product of graphs true false false Slovenski jezik Angleški jezik Magistrsko delo/naloga 2025-02-26 08:15:06 2025-02-26 08:15:10 2025-02-27 03:56:09 0000-00-00 00:00:00 2025 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17 150022 227238659 16660.pdf 16660.pdf 1 98A9DBA31C450E1F88939530F5C45AF9 d550c14b9dc8f584d7cfa1f027520d91f81db1f31a07f3d59c21e0270eb283b4 7f1964db-f410-11ef-b232-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=200107 Fakulteta za matematiko in fiziko 0 0 0