| | SLO | ENG | Piškotki in zasebnost

Večja pisava | Manjša pisava

Iskanje po katalogu digitalne knjižnice Pomoč

Iskalni niz: išči po
išči po
išči po
išči po
* po starem in bolonjskem študiju

Opcije:
  Ponastavi


1 - 7 / 7
Na začetekNa prejšnjo stran1Na naslednjo stranNa konec
1.
Distance-based Invariants and Measures in Graphs
Aleksander Kelenc, 2019, doktorska disertacija

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: 635; Prenosov: 78
.pdf Celotno besedilo (800,48 KB)

2.
Edge-transitive lexicographic and cartesian products
Wilfried Imrich, Ali Iranmanesh, Sandi Klavžar, Abolghasem Soltani, 2016, izvirni znanstveni članek

Opis: In this note connected, edge-transitive lexicographic and Cartesian products are characterized. For the lexicographic product ▫$G \circ H$▫ of a connected graph ▫$G$▫ that is not complete by a graph ▫$H$▫, we show that it is edge-transitive if and only if ▫$G$▫ is edge-transitive and ▫$H$▫ is edgeless. If the first factor of ▫$G \circ H$▫ is non-trivial and complete, then ▫$G \circ H$▫ is edge-transitive if and only if ▫$H$▫ is the lexicographic product of a complete graph by an edgeless graph. This fixes an error of Li, Wang, Xu, and Zhao (Appl. Math. Lett. 24 (2011) 1924--1926). For the Cartesian product it is shown that every connected Cartesian product of at least two non-trivial factors is edge-transitive if and only if it is the Cartesian power of a connected, edge- and vertex-transitive graph.
Ključne besede: edge-transitive graph, vertex-transitive graph, lexicographic product of graphs, Cartesian product of graphs
Objavljeno v DKUM: 31.03.2017; Ogledov: 639; Prenosov: 363
.pdf Celotno besedilo (150,33 KB)
Gradivo ima več datotek! Več...

3.
A characterization of the edge connectivity of direct products of graphs
Simon Špacapan, 2013, izvirni znanstveni članek

Opis: V članku dokažemo formulo za povezanost po povezavah direktnega produkta grafov. V formuli se povezanost po povezavah produkta izraža kot funkcija povezanosti po povezavah, najmanjše stopnje, števila povezav in dvodelne frustracije obeh faktorjev. Prav tako v članku opišemo strukturo najmanjših presečnih množic v direktnih produktih grafov.
Ključne besede: matematika, teorija grafov, direktni produkt, povezanost po povezavah, mathematics, graph theory, direct product, edge connectivity
Objavljeno v DKUM: 10.07.2015; Ogledov: 692; Prenosov: 87
URL Povezava na celotno besedilo

4.
The edge fault-diameter of Cartesian graph bundles
Iztok Banič, Rija Erveš, Janez Žerovnik, 2009, izvirni znanstveni članek

Opis: Kartezični svežnji so posplošitev krovnih grafov in kartezičnih grafovskih produktov. Naj bo ▫$G$▫ nek s povezavami ▫$k_G$▫-povezan graf in ▫${bar{mathcal{D}}_c(G)}$▫ največji premer podgrafov grafa ▫$G$▫ dobljenih z odstranitvijo $▫c < k_G$▫ povezav. Dokazano je, da je ▫${bar{mathcal{D}}_{a+b+1}(G)} le {bar{mathcal{D}}_a(F)} le {bar{mathcal{D}}_b(B)} + 1$▫, če je ▫$G$▫ grafovski sveženj z vlaknom ▫$F$▫ in bazo ▫$B$▫, ▫$a < k_F$▫, ▫$b < k_B▫$. Dokazano je tudi, da je povezanost s povezavami grafovskega svežnja ▫$G▫$ vsaj ▫$k_F + k_B$▫.
Ključne besede: matematika, teorija grafov, kartezični grafovski produkti, kartezični grafovski svežnji, povezavni okvarni premer, mathematics, graph theory, Cartesian graph products, Cartesian graph bundles, edge-fault diameter
Objavljeno v DKUM: 10.07.2015; Ogledov: 919; Prenosov: 75
URL Povezava na celotno besedilo

5.
On plane bipartite graphs without fixed edges
Khaled Salem, Sandi Klavžar, 2007, izvirni znanstveni članek

Opis: Povezava grafa ▫$H$▫, ki premore vsaj eno popolno prirejanje, je fiksna povezava, če bodisi pripada vsem popolnim prirejanjem v ▫$H$▫ bodisi nobenemu popolnemu prirejanju. Dokazano je, da je povezan, ravninski, dvodelni graf brez fiksnih povezav natanko tedaj, ko je rob vsakega lica alternirajoči cikel. Nadalje je poliheksagonalen fragment brez fiksnih povezav natanko tedaj, ko so robovi neskončnega lica in vseh nešesterokotniških lic alternirajoči cikli. Dobljeni rezultati predstavljajo razširitev rezultatov iz [F. Zhang, M. Zheng, Generalized hexagonal systems with each hexagon being resonant, Discrete Appl. Math. 36 (1992) 67-73] na posplošene haksagonalne sisteme.
Ključne besede: matematika, teorija grafov, popolno prirejanje, fiksna povezava, alternirajoči cikel, dvodelni ravninski graf, poliheksagonalen fragment, posplošen heksagonalen sistem, mathematics, graph theory, perfect matching, fixed edge, alternating cycle, plane bipartite graph, polyhex fragment, generalized hexagonal system
Objavljeno v DKUM: 10.07.2015; Ogledov: 823; Prenosov: 67
URL Povezava na celotno besedilo

6.
Characterizing flag graphs and induced subgraphs of Cartesian product graphs
Iztok Peterin, 2005, izvirni znanstveni članek

Opis: Točke zastavnega grafa ▫$Phi(P)$▫ so verige maksimalne dolžine stopničaste delno urejene množice ▫$P$▫. Dve točki sta sosedi natanko takrat, ko se njuni maksimalni verigi razlikujeta v enem elementu. V tem delu karakteriziramo zastavne grave stopničastih delno urejenih množic in inducirane podgrafe grafov kartezičnih produktov, pri čemer zastavni grafi kot razred ležijo med induciranimi in izometričnimi podgrafi Hammingovih grafov v strukturni teoriji. Pri obeh karakterizacijah uporabimo določena označevanja povezav grafa.
Ključne besede: matematika, teorija grafov, zastavni grafi, inducirani podgrafi, označevanje povezav, grafi kartezičnih produktov, kvocientni grafi, mathematics, graph theory, flag graphs, induced subgraphs, edge-labelings, Cartesian product graphs, quotient graphs
Objavljeno v DKUM: 10.07.2015; Ogledov: 610; Prenosov: 76
URL Povezava na celotno besedilo

7.
Characterizing subgraphs of Hamming graphs
Sandi Klavžar, Iztok Peterin, 2005, izvirni znanstveni članek

Opis: Kartezični produkti polnih grafov so znani kot Hammingovi grafi. Z uporabo vložitev v kartezične produkte kvocientnih grafov so karakterizirani podgrafi, inducirani podgrafi in izometrični podgrafi Hammingovih grafov. Na primer, graf ▫$G$▫ je inducirani podgraf Hammingovega grafa natanko tedaj, ko obstaja označitev povezav grafa ▫$G$▫, ki zadošča naslednjima pogojema: (i) povezave trikotnika imajo isto oznako, (ii) za vsaki točki ▫$u$▫ in ▫$v$▫ na razdalji vsaj 2 obstajata dve taki oznaki, ki se pojavita na vsaki inducirani poti med ▫$u$▫ in ▫$v$▫.
Ključne besede: matematika, teorija grafov, Hammingovi grafi, inducirani podgrafi, izometrični podgrafi, kartezični produkt grafov, označevanje povezav, kvocientni grafi, mathematics, graph theory, Hamming graphs, induced subgraphs, isometric subgraphs, edge-labelings, Cartesian products, quotient graphs
Objavljeno v DKUM: 10.07.2015; Ogledov: 705; Prenosov: 66
URL Povezava na celotno besedilo

Iskanje izvedeno v 0.12 sek.
Na vrh
Logotipi partnerjev Univerza v Mariboru Univerza v Ljubljani Univerza na Primorskem Univerza v Novi Gorici