Distance-based invariants and measures in graphs

doctoral dissertation

Aleksander Kelenc (Author), Andrej Taranenko (Mentor), Ismael G. Yero (Co-mentor)

Abstract

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.

Keywords

dissertations;Hausdorff distance;distance between graphs;graph algorithms;trees;graph similarity;edge metric dimension;edge metric generator;mixed metric dimension;metric dimension;

Data

Language:	English
Year of publishing:	2019
Typology:	2.08 - Doctoral Dissertation
Organization:	UM FNM - Faculty of Natural Sciences and Mathematics
Publisher:	A. Kelenc]
UDC:	519.173(043.3)
COBISS:	21679619
Views:	719
Downloads:	81
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	Slovenian
Secondary title:	Na razdaljah osnovane invariante in mere v grafih
Secondary abstract:	V doktorski disertaciji se posvetimo nekaterim temam, ki so povezane z razdaljami v grafih. Osredotočimo se na tri glavne teme, in sicer na pred kratkim vpeljano Hausdorffovo razdaljo med grafi in na dve novi grafovski invarianti - povezavno metrično dimenzijo grafa in mešano metrično dimenzijo grafa. Vse tri obravnavane teme spadajo v metrično teorijo grafov, saj so tesno povezane s konceptom razdalje med dvema vozliščema grafa. Hausdorffova razdalja med grafi je relativno nova mera podobnosti grafov. Določitev Hausdorffove razdalje med dvema grafoma temelji na posebnem skupnem pod grafu primerjanih grafov, ki ga določimo na podlagi strukturnih lastnosti zunaj samega skupnega pod grafa. V disertaciji obravnavamo Hausdorffovo razdaljo med nekaterimi družinami grafov, ki se pogosto pojavljajo v kemijski teoriji grafov. Poleg rezultatov za splošne grafe izračunamo formule za Hausdorffovo razdaljo med potmi in cikli. Do sedaj ni bil poznan noben učinkovit algoritem za reševanje problema določitve Hausdorffove razdalje med dvema drevesoma, v tej disertaciji pa predstavimo algoritem, ki reši omenjen problem v polinomskem času. Algoritem je rekurziven in uporablja strategijo reševanja problemov "deli in vladaj". Algoritem za reševanje enega od podproblemov uporablja tudi metodo, ki temelji na dobro poznanem algoritmu za iskanje največjega prirejanja v dvodelnem grafu. Povezavna metrična dimenzija je grafovska invarianta, ki se nanaša na razlikovanje povezav grafa. Naj bo $G=(V(G),E(G))$ povezan graf, naj bo $w \in V(G)$ vozlišče grafa in naj bo $e=uv \in E(G)$ povezava grafa. Razdalja med vozliščem $w$ in povezavo $e$ je določena z $d_G(e,w)=\min\{d_G(u,w),d_G(v,w)\}$. Vozlišče $w \in V(G)$ razlikuje povezavi $e_1,e_2\in E(G)$, če $d_G(w,e_1) \ne d_G(w,e_2)$. Množica vozlišč $S$ v povezanem grafu $G$ je povezavni metrični generator za $G$, če za vsaki dve različni povezavi grafa $G$ velja, da ju razlikuje neko vozlišče iz množice $S$. Moči najmanjšega povezavnega metričnega generatorja grafa $G$ rečemo povezavna metrična dimenzija in jo označimo z $dim_e(G)$. Povezavna metrična dimenzija je nov koncept. V disertaciji proučujemo njene matematične lastnosti. Skozi predstavitev rezultatov o obstoju grafov z vnaprej določeno povezavno metrično dimenzijo in standardno metrično dimenzijo naredimo primerjavo med obema. Dokažemo, da je izračun povezavne metrične dimenzije povezanih grafov NP-težek problem in podamo nekaj rezultatov o približnih rešitvah. Poleg tega predstavimo še meje in natančne formule za povezavno metrično dimenzijo številnih družin grafov. Mešana metrična dimenzija grafa je grafovska invarianta, ki je podobna povezavni metrični dimenziji. Nanaša se na razlikovanje elementov grafa (vozlišč in povezav). Vozlišče $w \in V(G)$ razlikuje dva elementa grafa $x,y \in E(G) \cup V(G)$, če $d_G(w,x) \ne d_G(w,y)$. Množica vozlišč $S$ v povezanem grafu $G$ je mešani metrični generator za $G$, če za vsaka dva elementa $x,y\in E(G)\cup V(G)$ grafa $G$, kjer $x \neq y$, velja, da ju razlikuje neko vozlišče iz množice $S$. Moči najmanjšega mešanega metričnega generatorja grafa $G$ rečemo mešana metrična dimenzija in jo označimo z $dim_m(G)$. V disertaciji obravnavamo strukturo mešanih metričnih generatorjev in podamo karakterizacijo grafov, za katere je mešana metrična dimenzija enaka naravnim spodnjim in zgornjim mejam. Podamo tudi rezultate za mešano metrično dimenzijo nekaterih družin grafov in predstavimo zgornjo mejo glede na ožino grafa. Na koncu dokažemo, da je izračun mešane metrične dimenzije povezanih grafov v splošnem NP-težek problem.
Secondary keywords:	disertacije;Hausdorffova razdalja;razdalja v grafih;algoritmi na grafih;drevesa;podobnost grafov;povezavna metrična dimenzija;povezavni metrični generator;mešana metrična dimenzija;metrična dimenzija;Grafi;Disertacije;Razdalje;Teorija grafov;
Type (COBISS):	Doctoral dissertation
Thesis comment:	Univ. v Mariboru, Fak. za naravoslovje in matematiko, Oddelek za matematiko in računalništvo
Pages:	VI, 138 str.
ID:	11327413