| | 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 / 17
Na začetekNa prejšnjo stran12Na naslednjo stranNa konec
1.
Weak k-reconstruction of Cartesian products
Wilfried Imrich, Blaž Zmazek, Janez Žerovnik, 2003, izvirni znanstveni članek

Opis: By Ulam's conjecture every finite graph ▫$G$▫ can be reconstructed from its deck of vertex deleted subgraphs. The conjecture is still open, but many special cases have been settled. In particular, one can reconstruct Cartesian products. We consider the case of ▫$k$▫-vertex deleted subgraphs of Cartesian products and prove that one can decide whether a graph ▫$H$▫ is a ▫$k$▫-vertex deleted subgraph of a Cartesian product ▫$G$▫ with at least ▫$k+1$▫ prime factors on at least ▫$k+1$▫ vertices each, and that ▫$H$▫ uniquely determines ▫$G$▫. This extends previous works of the authors and Sims. This paper also contains a counterexample to a conjecture of MacAvaney.
Ključne besede: mathematics, graph theory, reconstruction problem, Cartesian product, composite graphs
Objavljeno: 31.03.2017; Ogledov: 774; Prenosov: 280
.pdf Celotno besedilo (197,33 KB)
Gradivo ima več datotek! Več...

2.
Tree-like isometric subgraphs of hypercubes
Boštjan Brešar, Wilfried Imrich, Sandi Klavžar, 2003, izvirni znanstveni članek

Opis: Tree-like isometric subgraphs of hypercubes, or tree-like partial cubes as we call them, are a generalization of median graphs. Just as median graphs they capture numerous properties of trees, but may contain larger classes of graphs that may be easier to recognize than the class of median graphs. We investigate the structure of tree-like partial cubes, characterize them, and provide examples of similarities with trees and median graphs. For instance, we show that the cube graph of tree-like partial cube is dismantlable. This in particular implies that every tree-like partial cube ▫$G$▫ contains a cube that is invariant under every automorphism of ▫$G$▫. We also show that weak retractions preserve tree-like partial cubes, which in turn implies that every contraction of a tree-like partial cube fixes a cube. The paper ends with several Frucht-type results and a list of open problems.
Ključne besede: mathematics, graph theory, Isometric embeddings, partial cubes, expansion procedures, trees, median graphs, graph automorphisms, automorphism groups, dismantlable graphs
Objavljeno: 31.03.2017; Ogledov: 751; Prenosov: 274
.pdf Celotno besedilo (135,80 KB)
Gradivo ima več datotek! Več...

3.
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: 31.03.2017; Ogledov: 505; Prenosov: 328
.pdf Celotno besedilo (150,33 KB)
Gradivo ima več datotek! Več...

4.
NZ-flows in strong products of graphs
Wilfried Imrich, Iztok Peterin, Simon Špacapan, Cun-Quan Zhang, 2010, izvirni znanstveni članek

Opis: Za krepki produkt ▫$G_1 boxtimes G_2$▫ grafov ▫$G_1$▫ in ▫$G_2$▫ dokažemo, da je ▫${mathbb{Z}}_3$▫-pretočno kontraktibilen natanko tedaj, ko ▫$G_1 boxtimes G_2$▫ ni izomorfen ▫$Tboxtimes K_2$▫ (kar poimenujemo ▫$K_4$▫-drevo), kjer je ▫$T$▫ drevo. Sledi, da za ▫$G_1 boxtimes G_2$▫ obstaja NZ 3-pretok, razen če je ▫$G_1 boxtimes G_2$▫ ▫$K_4$▫-drevo. Dokaz je konstruktiven in implicira polinomski algoritem, ki nam vrne NZ 3-pretok, če ▫$G_1 boxtimes G_2$▫ ni ▫$K_4$▫-drevo, oziroma NZ 4-pretok sicer.
Ključne besede: matematika, teorija grafov, celoštevilski pretoki, krepki produkt, poti, cikli, nikjer ničelni pretok, mathematics, graph theory, integer flows, strong product, paths, cycles
Objavljeno: 10.07.2015; Ogledov: 478; Prenosov: 96
URL Povezava na celotno besedilo

5.
On the remoteness function in median graphs
Kannan Balakrishnan, Boštjan Brešar, Manoj Changat, Wilfried Imrich, Sandi Klavžar, Matjaž Kovše, Ajitha R. Subhamathi, 2009, izvirni znanstveni članek

Opis: Profil grafa ▫$G$▫ je poljubna neprazna multimnožica vozlišč iz ▫$G$▫. Pripadajoča funkcija oddaljenosti priredi vsakemu vozlišču iz ▫$V(G)$▫ vsoto razdalj do vozlišč iz profila. Najprej so dobljene nekatere uporabne lastnosti funkcije oddaljenosti na hiperkockah, nato pa je funkcija oddaljenosti obravnavana na poljubnih medianskih grafih glede na njihove izometrične vložitve v hiperkocke. V posebnem je najdena povezava med vozlišči medianskega grafa ▫$G$▫, katerega funkcija oddaljenosti je največja (antimedianska množica v ▫$G$▫), z antimediansko množico pripadajoče hiperkocke. Medtem ko je za lihe profile antimedianska množica neodvisna množica, ki leži na strogem robu medianskega grafa, obstajajo medianski grafi, v katerih določeni sodi profili porajajo konstantno funkcijo oddaljenosti. Take medianske grafe karakteriziramo na dva načina: kot grafe, katerih periferna transverzala je 2, in kot grafe z geodetskim številom 2. Nazadnje predstavimo algoritem, ki za dani graf ▫$G$▫ z ▫$n$▫ vozlišči in ▫$m$▫ povezavami v času ▫$O(m log n)$▫ odloči, ali je ▫$G$▫ medianski graf z geodetskim številom 2.
Ključne besede: hiperkocka, medianski graf, medianska množica, funkcija oddaljenosti, geodetsko število, periferna transverzala, median graph, median set, remoteness function, geodetic number, periphery transverzal, hypercube
Objavljeno: 10.07.2015; Ogledov: 604; Prenosov: 82
URL Povezava na celotno besedilo

6.
Transitive, locally finite median graphs with finite blocks
Wilfried Imrich, Sandi Klavžar, 2009, izvirni znanstveni članek

Opis: V članku obravnavamo neskončne, lokalno končne, vozliščno-tranzitivne medianske grafe. Pokazano je, da končnost ▫$Theta$▫-razredov takih grafov ne zagotavlja končnosti blokov. Bloki pa postanejo neskončni, če nadalje nobeno končno zaporedje ▫$Theta$▫-kontrakcij ne naredi novih prereznih vozlišč. Dokazano je, da obstaja končno mnogo vozliščno-tranzitivnih medianskih grafov fiksne stopnje, ki imajo končne bloke. Konstruirana je neskončna družina vozliščno-tranzitivnih medianskih grafov z intranzitivnimi bloki. Podan je tudi seznam vseh vozliščno-tranzitivnih medianskih grafov stopnje 4.
Ključne besede: teorija grafov, medianski grafi, neskočni grafi, vozliščno-tranzitivni grafi, graph theory, median graphs, infinite graphs, vertex-transitive graphs
Objavljeno: 10.07.2015; Ogledov: 684; Prenosov: 82
URL Povezava na celotno besedilo

7.
Lattice embeddings of trees
Wilfried Imrich, Matjaž Kovše, 2009, izvirni znanstveni članek

Opis: Predstavljen je algoritem časovno linearne zahtevnosti, ki na izometričen način vloži dano drevo ▫$T$▫ v celoštevilsko mrežo najmanjše možne dimenzije in omogoča izračun mrežnih koordinat vozlišč drevesa ▫$T$▫ v optimalnem času.
Ključne besede: matematika, teorija grafov, drevo, izometrična vložitev, mrežna vložitev, delna kocka, mathematics, graph theory, lattice embedding, isometric embedding, partial cube, tree
Objavljeno: 10.07.2015; Ogledov: 467; Prenosov: 61
URL Povezava na celotno besedilo

8.
The distinguishing number of Cartesian products of complete graphs
Wilfried Imrich, Janja Jerebic, Sandi Klavžar, 2008, objavljeni znanstveni prispevek na konferenci

Opis: Razlikovalno število ▫$D(G)$▫ grafa ▫$G$▫ je najmanjše število ▫$d$▫, tako da ▫$G$▫ premore označitev z ▫$d$▫ oznakami, ki jo ohranja le trivialni avtomorfizem. Dokažemo, da lahko kartezične produkte relativno tujih grafov, katerih velikosti se ne razlikujejo preveč, razlikujemo z majhnim številom barv. Za vse ▫$k$▫ in ▫$n$▫ določimo razlikovalno število kartezičnega produkta ▫$K_k square K_k$▫ in sicer bodisi eksplicitno, bodisi s kratko rekurzijo. Vpeljemo tudi stolpčno-invariantne množice vektorjev in dokažemo preklopno lemo, ki igra ključno vlogo v dokazih.
Ključne besede: matematika, teorija grafov, razlikovalno število, polni grafi, kartezični produkt grafov, mathematics, graph theory, distingushing number, complete graphs, Cartesian product
Objavljeno: 10.07.2015; Ogledov: 578; Prenosov: 51
URL Povezava na celotno besedilo

9.
Transitive, locally finite median graphs with finite blocks
Wilfried Imrich, Sandi Klavžar, 2008

Opis: V članku obravnavamo neskončne, lokalno končne, vozliščno-tranzitivne medianske grafe. Pokazano je, da končnost ▫$Theta$▫-razredov takih grafov ne zagotavlja končnosti blokov. Bloki pa postanejo neskončni, če nadalje nobeno končno zaporedje ▫$Theta$▫-kontrakcij ne naredi novih prereznih vozlišč. Dokazano je, da obstaja končno mnogo vozliščno-tranzitivnih medianskih grafov fiksne stopnje, ki imajo končne bloke. Konstruirana je neskončna družina vozliščno-tranzitivnih medianskih grafov z intranzitivnimi bloki. Podan je tudi seznam vseh vozliščno-tranzitivnih medianskih grafov stopnje 4.
Ključne besede: teorija grafov, medianski grafi, neskočni grafi, vozliščno-tranzitivni grafi, graph theory, median graphs, infinite graphs, vertex-transitive graphs
Objavljeno: 10.07.2015; Ogledov: 684; Prenosov: 71
URL Povezava na celotno besedilo

10.
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: 612; Prenosov: 67
URL Povezava na celotno besedilo

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