20.500.12556/RUL-168423 Metrična dimenzija leksikografskega produkta grafov delo diplomskega seminarja The Metric Dimension of the Lexicographic Product of Graphs Metrična dimenzija grafa je definirana kot najmanjša moč množice vozlišč, ki enolično določa položaj vsakega vozlišča v grafu glede na njegove razdalje do vozlišč iz te množice. Leksikografski produkt grafov $G$ in $H$, označen z $G \circ H$, je graf z množico vozlišč $V(G) \times V(H)$, kjer sta vozlišči $(a,v)$ in $(b,w)$ sosednji, če velja $ab \in E(G)$ ali $a=b$ in $vw \in E(H)$. Meje metrične dimenzije leksikografskega produkta $G \circ H$, kjer je $G$ povezan, so odvisne od reda grafa $G$, števila komponent grafa $H$, metričnih dimenzij komponent grafa $H$ in metričnih dimenzij spojev komponent grafa $H$ z grafom $K_1$. Sosedska dimenzija grafa je definirana kot najmanjša moč množice vozlišč, ki enolično določa položaj vsakega vozlišča v grafu glede na njegovo sosednost do vozlišč iz te množice. Vozlišči $u$ in $v$ sta dvojčka, če velja $N(u) \setminus \{v\} = N(v) \setminus \{u\}$, kjer $N(u)$ označuje soseščino vozlišča $u$. To je ekvivalenčna relacija in njeni ekvivalenčni razredi so lahko treh različnih tipov. Če poznamo lastnosti sosedskih baz grafa $H$ in števila ekvivalenčnih razredov različnih tipov glede na relacijo dvojčkov v grafu $G$, lahko metrično dimenzijo grafa $G \circ H$ eksplicitno izračunamo. The metric dimension of a graph is defined as the smallest size of a set of vertices that uniquely determines the position of every vertex in the graph based on its distances to the vertices in that set. The lexicographic product of graphs $G$ and $H$, denoted by $G \circ H$, is a graph with the vertex set $V(G) \times V(H)$, where two vertices $(a,v)$ and $(b,w)$ are adjacent if $ab \in E(G)$ or $a=b$ and $vw \in E(H)$. The bounds of the metric dimension of the lexicographic product $G \circ H$, where $G$ is connected, depend on the order of the graph $G$, the number of components of the graph $H$, the metric dimensions of the components of the graph $H$, and the metric dimensions of joint graphs $H_i + K_1$, where $H_i$ are components of graph $H$. The adjacency dimension of a graph is defined as the smallest size of a set of vertices that uniquely determines the position of every vertex in the graph based on its adjacency to the vertices in that set. Vertices $u$ and $v$ are twins if $N(u) \setminus \{v\} = N(v) \setminus \{u\}$, where $N(u)$ denotes the neighborhood of vertex $u$. This is an equivalence relation, and its equivalence classes can be of three different types. If the properties of the neighborhood bases of the graph $H$ and the number of equivalence classes of different types with respect to the twin relation in the graph $G$ are known, we can give explicit formula for the metric dimension of the graph $G \circ H$. graf metrična dimenzija sosedska dimenzija dvojčki leksikografski produkt graph metric dimension adjacency dimension twins lexicographic product true false false Slovenski jezik Angleški jezik Delo diplomskega seminarja/zaključno seminarsko delo/naloga 2025-04-12 08:16:01 2025-04-12 08:16:06 2025-07-10 13:58:49 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 150156 232482051 16726.pdf 16726.pdf 1 6BD49539C3FFC404D0E3D107F12296AD 43b1f1a847d467462665dcaae4052020d71be8a0133aa79743dd24e9944ee899 84496834-1764-11f0-b232-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=201832 Fakulteta za matematiko in fiziko 0 0 0