| | 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 - 10 / 13
Na začetekNa prejšnjo stran12Na naslednjo stranNa konec
1.
2.
Wide diameter of Cartesian graph bundles
Iztok Banič, Janez Žerovnik, 2010, objavljeni znanstveni prispevek na konferenci

Opis: Fault tolerance and transmission delay of networks are important concepts in network design. The notions are strongly related to connectivity and diameter of a graph, and have been studied by many authors. Wide diameter of a graph combines studying connectivity with the diameter of a graph. Diameter with width ▫$k$▫ of a graph ▫$G$▫, ▫$k$▫-diameter, is defined as the minimum integer ▫$d$▫ for which there exist at least ▫$k$▫ internally disjoint paths of length at most ▫$d$▫ between any two distinct vertices in ▫$G$▫. Denote by ▫${mathscr D}_c(G)$▫ the ▫$c$▫-diameter of ▫$G$▫ and ▫$kappa(G)$▫ the connectivity of ▫$G$▫. In the context of computer networks, wide diameters of Cartesian graph products have been recently studied by many authors. Cartesian graph bundles is a class of graphs that is a generalization of the Cartesian graph products. Let ▫$G$▫ be a Cartesian graph bundle with fiber ▫$F$▫ over base ▫$B$▫, ▫$0 < a le kappa(F)$▫, and ▫$0 < b le kappa(B)$▫. We prove that ▫${mathscr D}_{a+b}(G) le {mathscr D}_a(F) + {mathscr D}_b(B) + 1$▫. Moreover, if ▫$G$▫ is a graph bundle with fiber ▫$F ne K_2$▫ over base ▫$B ne K_2$▫, then ▫${mathscr D}_{a+b}(G) le {mathscr D}_a(F) + {mathscr D}_b(B)$▫. The bounds are tight.
Ključne besede: mathematics, graph theory, Cartesian graph products, Cartesian graph bundles, wide diameter
Objavljeno: 07.06.2012; Ogledov: 938; Prenosov: 29
URL Povezava na celotno besedilo

3.
Distance-balanced graphs
Janja Jerebic, Sandi Klavžar, Douglas F. Rall, 2005

Opis: V članku so vpeljani razdaljno uravnoteženi grafi kot grafi, v katerih ima vsaka povezava ▫$uv$▫ naslednjo lastnost: število točk, ki so bližje ▫$u$▫ kot ▫$v$▫, je enako kot število točk, ki so bližje ▫$v$▫ kot ▫$u$▫. Dobljene so osnovne lastnosti teh grafov. Novi koncept je povezan z grafovskimi simetrijami, študirane so tudi lokalne operacije na grafih glede na razdaljno uravnoteženost. Karakterizirani so razdaljno uravnoteženi kartezični in leksikografski produkti grafov. Postavljenih je več odprtih problemov.
Ključne besede: matematika, teorija grafov, razdalja, razdaljno uravnoteženi grafi, produkti grafov, povezanost, mathematics, graph theory, graph distance, distance-balanced graphs, graph products, connectivity
Objavljeno: 10.07.2015; Ogledov: 429; Prenosov: 31
URL Povezava na celotno besedilo

4.
Fault-diameter of Cartesian product of graphs and Cartesian graph bundles
Iztok Banič, Janez Žerovnik, 2006

Opis: Cartesian graph bundles is a class of graphs that is a generalization of the Cartesian graph products. Let ▫$G$▫ be a ▫$k_G$▫-connected graph and ▫${mathcal{D}}_c(G)$▫ denote the diameter of ▫$G$▫ after deleting any of its ▫$c < k_G$▫ vertices. We prove that if ▫$G_1, G_2, dots, G_q$▫ are ▫$k_1$▫-connected, ▫$k_2$▫-connected,...,▫$k_q$▫-connected graphs and ▫$0 leq a_1 < k_1$▫, ▫$0 leq a_2 < k_2$▫,...,▫$0 leq a_q < k_q$▫ and ▫$a = a_1 + a_2 + dots + a_q + (q-1)$▫, then the fault diameter of ▫$G$▫, a Cartesian product of ▫$G_1$▫, ▫$G_2$▫,...,▫$G_q$▫, with ▫$a$▫ faulty nodes is ▫${mathcal{D}}_{a}(G) leq {mathcal{D}}_{a_1}(G_1)+{mathcal{D}}_{a_2}(G_2) + dots + {mathcal{D}}_{a_q}(G_q) + 1$▫. We also show that ▫${mathcal{D}}_{a+b+1}(G) leq {mathcal{D}}_a(F) + {mathcal{D}}_b(B) + 1$▫ if ▫$G$▫ is a graph bundle with fibre ▫$F$▫ over base ▫$B$▫, ▫$a leq k_F$▫, and ▫$b leq k_B$▫. As an auxiliary result we prove that connectivity of graph bundle ▫$G$▫ is at least ▫$k_F+k_B$▫.
Ključne besede: mathematics, graph theory, Cartesian graph bundles, Cartesian graph products, fault diameter, interconnection network
Objavljeno: 10.07.2015; Ogledov: 310; Prenosov: 13
URL Povezava na celotno besedilo

5.
On the k-path vertex cover of some graph products
Marko Jakovac, Andrej Taranenko, 2013, izvirni znanstveni članek

Opis: A subset S of vertices of a graph G is called a k-path vertex cover if every path of order k in G contains at least one vertex from S. Denote by ▫$psi_k$▫(G) the minimum cardinality of a k-path vertex cover in G. In this paper, improved lower and upper bounds for ▫$psi_k$▫ of the Cartesian and the strong product of paths are derived. It is shown that for ▫$psi_3$▫ those bounds are tight. For the lexicographic product bounds are presented for ▫$psi_k$▫, moreover ▫$psi_2$▫ and ▫$psi_3$▫ are exactly determined for the lexicographic product of two arbitrary graphs. As a consequence the independence and the dissociation number of the lexicographic product are given.
Ključne besede: matematika, teorija grafov, vozliščno pokritje, po poteh vozliščno pokritje, disociacijsko število, neodvisnostno število, grafovski produkti, mathematics, graph theory, vertex cover, path vertex cover, dissociation number, independence number, graph products
Objavljeno: 10.07.2015; Ogledov: 386; Prenosov: 5
URL Povezava na celotno besedilo

6.
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: 10.07.2015; Ogledov: 328; Prenosov: 17
URL Povezava na celotno besedilo

7.
Distinguishing Cartesian powers of graphs
Wilfried Imrich, Sandi Klavžar, 2006, izvirni znanstveni članek

Opis: Razlikovalno število ▫$D(G)$▫ grafa je najmanjše celo število ▫$d$▫, za katero obstaja taka ▫$d$▫-označitev točk grafa ▫$G$▫, da je ne ohranja noben avtomorfizem grafa ▫$G$▫. Dokažemo, da je razlikovalno število kvadrata in višjih potenc povezanega grafa ▫$G ne K_2, K_3$▫, glede na kartezični produkt, vedno enako 2. Ta rezultat je močnejši od rezultatov Albertsona [Electron J Combin, 12 (2005), N17] za potence pra-grafov in tudi od rezultatov Klavžarja and Zhuja [European J. Combin, v tisku]. Bolj splošno, dokažemo tudi, da je ▫$(G Box H) = 2$▫, če sta ▫$G$▫ in ▫$H$▫ relativno tuja grafa in je ▫$|H| le |G| < 2^{|H|} - |H|$▫. Pod podobnimi pogoji veljajo sorodni rezultati tudi za potence grafov glede na krepki in direktni produkt grafov.
Ključne besede: matematika, teorija grafov, razlikovalno število, grafovski avtomorfizem, produkti grafov, mathematics, graph theory, distingushing number, graph automorphism, products of graphs
Objavljeno: 10.07.2015; Ogledov: 273; Prenosov: 20
URL Povezava na celotno besedilo

8.
Cartesian powers of graphs can be distinguished by two labels
Sandi Klavžar, Xuding Zhu, 2007, izvirni znanstveni članek

Opis: The distinguishing number ▫$D(G)$▫ of a graph ▫$G$▫ is the least integer ▫$d$▫ such that there is a ▫$d$▫-labeling of the vertices of ▫$G$▫ which is not preserved by any nontrivial automorphism. For a graph ▫$G$▫ let ▫$G^r$▫ be the ▫$r$▫-th power of ▫$G$▫ with respect to the Cartesian product. It is proved that ▫$D(G^r) = 2$▫ for any connected graph ▫$G$▫ with at least 3 vertices and for any ▫$r = 3$▫. This confirms and strengthens a conjecture of Albertson. Other graph products are also considered and a refinement of the Russell and Sundaram motion lemma is proved.
Ključne besede: matematika, teorija grafov, razlikovalno število, grafovski avtomorfizem, produkti grafov, mathematics, graph theory, distingushing number, graph automorphism, products of graphs
Objavljeno: 10.07.2015; Ogledov: 284; Prenosov: 21
URL Povezava na celotno besedilo

9.
Cancellation properties of products of graphs
Wilfried Imrich, Sandi Klavžar, Douglas F. Rall, 2007, kratki znanstveni prispevek

Opis: V tem kratkem prispevku razširimo rezultate Fernándeza, Leightona in López-Presa o enoličnosti ▫$r$▫-tih korenov nepovezanih grafov glede na kartezični produkt na druge produkte in pokažemo, da lahko z njihovimi metodami izpeljemo nova pravila krajšanja.
Ključne besede: matematika, teorija grafov, produkti grafov, pravilo krajšanja, enoličnost korenov, mathematics, graph theory, graph products, cancellation property, uniqueness of roots
Objavljeno: 10.07.2015; Ogledov: 341; Prenosov: 21
URL Povezava na celotno besedilo

10.
Distance-balanced graphs
Janja Jerebic, Sandi Klavžar, Douglas F. Rall, 2008, izvirni znanstveni članek

Opis: V članku so vpeljani razdaljno uravnoteženi grafi kot grafi, v katerih ima vsaka povezava ▫$uv$▫ naslednjo lastnost: število točk, ki so bližje ▫$u$▫ kot ▫$v$▫, je enako kot število točk, ki so bližje ▫$v$▫ kot ▫$u$▫. Dobljene so osnovne lastnosti teh grafov. Novi koncept je povezan z grafovskimi simetrijami, študirane so tudi lokalne operacije na grafih glede na razdaljno uravnoteženost. Karakterizirani so razdaljno uravnoteženi kartezični in leksikografski produkti grafov. Postavljenih je več odprtih problemov.
Ključne besede: matematika, teorija grafov, razdalja, razdaljno uravnoteženi grafi, produkti grafov, povezanost, mathematics, graph theory, graph distance, distance-balanced graphs, graph products, connectivity
Objavljeno: 10.07.2015; Ogledov: 338; Prenosov: 29
URL Povezava na celotno besedilo

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