Metrična dimenzija leksikografskega produkta grafovMurn, Manca (Avtor) Klavžar, Sandi (Mentor) grafmetrična dimenzijasosedska dimenzijadvojčkileksikografski produktMetrič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.20252025-04-12 08:16:01Delo diplomskega seminarja/zaključno seminarsko delo/naloga168423sl