20.500.12556/RUL-161233 Koalicijski grafi poti in ciklov delo diplomskega seminarja Coalition graphs of paths and cycles Koalicija v grafu $G = (V(G), E(G))$ je par nedominantnih disjunktnih množic $V_1 \subseteq V(G)$ in $V_2 \subseteq V(G)$, katerih unija $V_1 \cup V_2$ je dominantna množica grafa $G$. Koalicijska razdelitev grafa $G$ je takšna razdelitev vozlišč $\pi = (V_1, V_2, \ldots, V_k)$, da je vsaka množica $V_i \in \pi$ bodisi dominantna in sestavljena iz enega vozlišča (stopnje $|V(G)| - 1$) bodisi nedominantna in tvori koalicijo z neko drugo nedominantno množico $V_j \in \pi$. Koalicijski graf grafa $G$ glede na koalicijsko razdelitev $\pi$ je graf $CG(G, \pi)$, ki ima za vozlišča množice $V_1, \ldots, V_k \in \pi$, vozlišči pa sta sosednji natanko tedaj, ko pripadajoči množici $V_i, V_j \in \pi$ tvorita koalicijo. V tem delu bomo opredelili koalicijske grafe poti in ciklov. Pokazali bomo, da je teh le končno mnogo, in natančno določili, kateri grafi so to. A coalition in graph $G = (V(G), E(G))$ is a pair of two non-dominating disjoint sets $V_1 \subseteq V(G)$ and $V_2 \subseteq V(G)$, whose union $V_1 \cup V_2$ is a dominating set of $G$. A coalition partition in a graph $G$ is a vertex partition $\pi = (V_1, V_2, \ldots, V_k)$ such that every set $V_i \in \pi$ either is a dominating set consisting of a single (full) vertex, or is not a dominating set but forms a coalition with another non-dominating set $V_j \in \pi$. A coalition graph of graph $G$ with respect to the coalition partition $\pi$ is a graph $CG(G, \pi)$, the vertices of which correspond one-to-one with the sets $V_1, V_2, \ldots, V_k$ of $\pi$ and two vertices are adjacent in $CG(G, \pi)$ if their corresponding sets in $\pi$ form a coalition. In this paper we characterize the coalition graphs of paths and cycles. We show that there are only finitely many coalition graphs of paths and finitely many coalition graphs of cycles and we identify precisely which they are. razdelitev množice vozlišč dominantna množica koalicija koalicijska razdelitev koalicijski graf vertex partition dominating set coalition coalition partition coalition graph true false false Slovenski jezik Angleški jezik Delo diplomskega seminarja/zaključno seminarsko delo/naloga 2024-09-08 08:15:19 2024-09-08 08:15:23 2024-09-16 10:17:02 0000-00-00 00:00:00 2024 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17 142693 207624195 12892.pdf 12892.pdf 1 880871B2D2240EB76CAA9C9A26920A95 384593d2d5f5bc2155359818157b16eb2e772210b870f0a2234b5c59c7b27e78 b32c44f7-6da9-11ef-b232-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=190120 Fakulteta za matematiko in fiziko 0 0 0