Iskanje po katalogu digitalne knjižnice

Opis: The Wiener index of a connected graph ▫$G$▫ is the sum of distances between all pairs of vertices of ▫$G$▫. The strong product is one of the four most investigated graph products. In this paper the general formula for the Wiener index of the strong product of connected graphs is given. The formula can be simplified if both factors are graphs with the constant eccentricity. Consequently, closed formulas for the Wiener index of the strong product of a connected graph ▫$G$▫ with a cycle are derived.
Ključne besede: Wiener index, graph product, strong product
Objavljeno v DKUM: 30.11.2017; Ogledov: 1479; Prenosov: 429
Celotno besedilo (424,67 KB)
Gradivo ima več datotek! Več...

Opis: The strong product ▫$G_1 \boxtimes G_2$▫ of graphs ▫$G_1$▫ and ▫$G_2$▫ is the graph with ▫$V(G_1) \times V(G_2)$▫ as the vertex set, and two distinct vertices ▫$(x_1,x_2)$▫ and ▫$(y_1,y_2)$▫ are adjacent whenever for each ▫$i\in \{1,2\}$▫ either ▫$x_i=y_i$▫ or ▫$x_iy_i \in E(G_i)$▫. In this note we show that for two connected graphs ▫$G_1$▫ and ▫$G_2$▫ the edge-connectivity ▫$\lambda(G_1 \boxtimes G_2)$▫ equals ▫$\min\{\delta(G_1\boxtimes G_2), \lambda(G_1)(|V(G_2)|+2|E(G_2)|), \lambda(G_2)(|V(G_1)|+2|E(G_1)|)\}$▫. In addition, we fully describe the structure of possible minimum edge cut sets in strong products of graphs.
Ključne besede: mathematics, graph theory, connectivity, strong product, graph product, separating set
Objavljeno v DKUM: 31.03.2017; Ogledov: 1447; Prenosov: 374
Celotno besedilo (173,26 KB)
Gradivo ima več datotek! Več...

Opis: Pravilno barvanje vozlišč grafa kjer vsak barvni razred vsebuje vozlišče, ki ima soseda v vseh preostalih barvnih razredih, imenujemo b-barvanje. Največje naravno število ▫$varphi (G)$▫, za katero obstaja b-barvanje grafa ▫$G$▫, imenujemo b-kromatično število. Določimo nekatere spodnje in zgornje meje b-kromatičnega števila za krepki produkt ▫$G,boxtimes, H$▫, leksikografski produkt ▫$G[H]$▫ in za direktni produkt ▫$G,times, H$▫. Prav tako določimo nekatere točne vrednosti za produkte poti, ciklov, zvezd in polnih dvodelnih grafov. Pokažemo tudi, da lahko določimo b-kromatično število za ▫$P_n ,boxtimes, H$▫, ▫$C_n ,boxtimes, H$▫, ▫$P_n[H]$▫, ▫$C_n[H]$▫ in ▫$K_{m,n}[H]$▫ za poljuben graf ▫$H$▫, če sta le ▫$m$▫ in ▫$n$▫ dovolj veliki.
Ključne besede: teorija grafov, b-kromatično število, krepki produkt, leksikografski produkt, direktni produkt, graph theory, b-chromatic number, strong product, lexicographic product, direct product
Objavljeno v DKUM: 10.07.2015; Ogledov: 1190; Prenosov: 90
Povezava na celotno besedilo

Opis: Krepka izometrična dimenzija grafa ▫$G$▫ je najmanjše število ▫$k$▫, tako da lahko ▫$G$▫ izometrično vložimo v krepki produkt ▫$k$▫ poti. Z uporabo Spernerjevega izreka je določena krepka izometrična dimenzija Hammingovih grafov ▫$K_2,{square}, K_n$▫.
Ključne besede: matematika, teorija grafov, krepka izometrična dimenzija, Hammingovi grafi, mathematics, graf theory, strong product, Hamming graphs
Objavljeno v DKUM: 10.07.2015; Ogledov: 1007; Prenosov: 77
Povezava na celotno besedilo

Opis: The strong isometric dimension and the adjacent isometric dimension of graphs are compared. The concepts are equivalent for graphs of diameter 2 in which case the problem of determining these dimensions can be reduced to a covering problem with complete bipartite graphs. Using this approach several exact strong and adjacent dimensions are computed (for instance of the Petersen graph) and a positive answer is given to the Problem 4.1 of Fitzpatrick and Nowakowski [The strong isometric dimension of finite reflexive graphs, Discuss. Math. Graph Theory 20 (2000) 23-38] whether there is a graph ▫$G$▫ with the strong isometric dimension bigger that ▫$lceil |V(G)|/2 rceil$▫.
Ključne besede: mathematics, graph theory, strong product of graphs, adjacent isometric dimension, strong isometric dimension
Objavljeno v DKUM: 10.07.2015; Ogledov: 1208; Prenosov: 122
Povezava na celotno besedilo