Iskanje po katalogu digitalne knjižnice

Opis: This doctoral dissertation is concerned with aspects on distance related topics in graphs. We study three main topics, namely a recently introduced measure called the Hausdorff distance of graphs and two new graph invariants - the edge metric dimension and the mixed metric dimension of graphs. All three topics are part of the metric graph theory since they are tightly connected with the basic concept of distance between two vertices of a graph. The Hausdorff distance is a relatively new measure of the similarity of graphs. The notion of the Hausdorff distance considers a special kind of common subgraph of the compared graphs and depends on the structural properties outside of the common subgraph. We study the Hausdorff distance between certain families of graphs that often appear in chemical graph theory. Next to a few results for general graphs, we determine formulae for the distance between paths and cycles. Previously, there was no known efficient algorithm for the problem of determining the Hausdorff distance between two trees, and in this dissertation we present a polynomial-time algorithm for it. The algorithm is recursive and it utilizes the divide and conquer technique. As a subtask it also uses a procedure that is based on the well-known graph algorithm for finding a maximum bipartite matching. The edge metric dimension is a graph invariant that deals with distinguishing the edges of a graph. Let $G=(V(G),E(G))$ be a connected graph, let $w \in V(G)$ be a vertex, and let $e=uv \in E(G)$ be an edge. The distance between the vertex $w$ and the edge $e$ is given by $d_G(e,w)=\min\{d_G(u,w),d_G(v,w)\}$. A vertex $w \in V(G)$ distinguishes two edges $e_1,e_2 \in E(G)$ if $d_G(w,e_1) \ne d_G(w,e_2)$. A set $S$ of vertices in a connected graph $G$ is an edge metric generator of $G$ if every two distinct edges of $G$ are distinguished by some vertex of $S$. The smallest cardinality of an edge metric generator of $G$ is called the edge metric dimension and is denoted by $dim_e(G)$. The concept of the edge metric dimension is new. We study its mathematical properties. We make a comparison between the edge metric dimension and the standard metric dimension of graphs while presenting some realization results concerning the two. We prove that computing the edge metric dimension of connected graphs is NP-hard and give some approximation results. Moreover, we present bounds and closed formulae for the edge metric dimension of several classes of graphs. The mixed metric dimension is a graph invariant similar to the edge metric dimension that deals with distinguishing the elements (vertices and edges) of a graph. A vertex $w \in V(G)$ distinguishes two elements of a graph $x,y \in E(G)\cup V(G)$ if $d_G(w,x) \ne d_G(w,y)$. A set $S$ of vertices in a connected graph $G$ is a mixed metric generator of $G$ if every two elements $x,y \in E(G) \cup V(G)$ of $G$, where $x \neq y$, are distinguished by some vertex of $S$. The smallest cardinality of a mixed metric generator of $G$ is called the mixed metric dimension and is denoted by $dim_m(G)$. In this dissertation, we consider the structure of mixed metric generators and characterize graphs for which the mixed metric dimension equals the trivial lower and upper bounds. We also give results on the mixed metric dimension of certain families of graphs and present an upper bound with respect to the girth of a graph. Finally, we prove that the problem of determining the mixed metric dimension of a graph is NP-hard in the general case.
Ključne besede: Hausdorff distance, distance between graphs, graph algorithms, trees, graph similarity, edge metric dimension, edge metric generator, mixed metric dimension, metric dimension
Objavljeno v DKUM: 03.08.2020; Ogledov: 1584; Prenosov: 120
Celotno besedilo (800,48 KB)

Opis: In a recent work [Chem. Phys. Lett. 333 (2001) 319-321] Nikolić, Trinajstić, and Randie put forward a novel modification ▫$^m$▫W of the Wiener index. We now show that ▫$^m$▫W possesses the basic properties required by a topological index to be acceptable as a measure of the extent of branching of the carbon-atom skeleton of the respective molecule (and therefore to be a structure-descriptor, potentially applicable in QSPR and QSAR studies). In particular, if ▫$T_n$▫ is any n-vertex tree, different from the n-vertex path ▫$P_n$▫ and the n-vertex star ▫$S_n$▫, then mw(Pn) < mW(Tn) < mW(Sn). We also show how the concept of the modified Wiener index can be extended to weighted molecular graphs.
Ključne besede: graph theory, distance, molecular graphs, modified Wiener index, weigted modified Wiener index, branching, chemical graph theory
Objavljeno v DKUM: 05.07.2017; Ogledov: 1141; Prenosov: 84
Celotno besedilo (85,05 KB)
Gradivo ima več datotek! Več...

Opis: Naj bo ▫$I_G(x,y)$▫ interval najkrajših ▫$x,y$▫-poti in ▫$J_G(x,y)$▫ interval induciranih ▫$x,y$▫-poti v povezanem grafu ▫$G$▫. Obravnavani so naslednji trije aksiomi vmesnosti za množico ▫$V$▫ in ▫$R: V times V rightarrow 2^V$▫: (i) ▫$x in R(u,y), y in R(x,v), x neq y, |R(u,v)|>2 Rightarrow x in R(u,v)$▫; (ii) ▫$x in R(u,v) Rightarrow R(u,x) cap R(x,v) = {x}$▫; (iii) ▫$x in R(u,y), y in R(x,v), x neq y, Rightarrow x in R(u,v)$▫. Karakteriziramo razred grafov, za katere ▫$I_G$▫ izpolnjuje (i), razred grafov, za katere ▫$J_G$▫ izpolnjuje (ii) in razred grafov, kjer oba ▫$I_G$▫ in ▫$J_G$▫ izpolnjujeta (iii). Karakterizacije so podane z prepovedanimi induciranimi podgrafi. Izkaže se, da je razred grafov, kjer ▫$I_G$▫ izpolnjuje (i), pravi podrazred razdaljno dednih grafov in da je razred, kjer ▫$J_G$▫ izpolnjuje (ii), pravi nadrazred razdaljno dednih grafov. Podani sta tudi aksiomatični karakterizaciji tetivnih in ptolomejskih grafov.
Ključne besede: matematika, teorija grafov, prepovedani podgrafi, inducirana pot, intervalna funkcija, aksiomi vmesnosti, tetivni grafi, razdaljno dedni grafi, mathematics, graph theory, forbidden subgraphs, induced path, interval function, betweenness axioms, chordal graphs, distance hereditary graphs
Objavljeno v DKUM: 10.07.2015; Ogledov: 1306; Prenosov: 103
Povezava na celotno besedilo

Opis: Za dani graf ▫$G$▫ je Steinerjev interval množice vozlišč ▫$W subset V(G)$▫ množica tistih vozlišč, ki ležijo na kakem Steinerjevem drevesu glede na ▫$W$▫. Množica ▫$U subset V(G)$▫ je ▫$g_3$▫-konveksna v ▫$G$▫, če Steinerjev interval poljubne trojice vozlišč iz ▫$U$▫ v celoti leži v ▫$U$▫. Henning, Nielsen in Oellermann (2009) so dokazali, da graf ▫$G$▫, v katerem so ▫$j$▫-krogle ▫$g_3$▫-konveksne za vsak ▫$j ge 1$▫, ne vsebuje hiše niti grafov dvojčkov ▫$C_4$▫ kot induciranih podgrafov in vsak cikel v ▫$G$▫ dolžine vsaj šest je dobro premostljiv. V tem članku dokažemo, da velja tudi obrat tega izreka, s čimer okarakteriziramo grafe z ▫$g_3$▫-konveksnimi kroglami.
Ključne besede: matematika, teorija grafov, Steinerjev interval, razdalja, dobra premostljivost, mathematics, graph theory, Steiner interval, distance, well-bridgeness
Objavljeno v DKUM: 10.07.2015; Ogledov: 1062; Prenosov: 49
Povezava na celotno besedilo

Opis: We show how to compute in ▫$O(n^{4/3} log^{1/3} n + n^{2/3}k^{2/3} log n)$▫ time the distance between $k$ given pairs of vertices of a planar graph $G$ with ▫$n$▫ vertices. This improves previous results whenever ▫$(n/log n)^{5/6} le k le n^2/log^6 n$▫. As an application, we speed up previous algorithms for computing the dilation of geometric planar graphs.
Ključne besede: matematika, teorija grafov, ravninski graf, razdalja, mathematics, graph theory, planar graph, distance
Objavljeno v DKUM: 10.07.2015; Ogledov: 1401; Prenosov: 77
Povezava na celotno besedilo