| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

Search the digital library catalog Help

Query: search in
search in
search in
search in
* old and bologna study programme

Options:
  Reset


1 - 10 / 17
First pagePrevious page12Next pageLast page
1.
Relations between median graphs, semi-median graphs and partial cubes
Wilfried Imrich, Sandi Klavžar, Henry Martyn Mulder, Riste Škrekovski, 1998

Abstract: Podan je samostojen dokaz ekspanzijskega izreka za semi-medianske grafe. Dokazano je, da te grafe lahko karakteriziramo kot tlakovane delne kocke in da za njih velja neenakost ▫$2n-m-k le 2$▫. Pri tem je ▫$k$▫ število ekvivalenčnih razredov relacije ▫$Theta$▫. Za medianske grafe dokažemo, da se dajo karakterizirati kot semi-medianski grafi brez ▫$Q_3^-$▫. Vpeljemo tudi koncept šibke 2-konveksnosti in jo uporabimo, med drugim, za dokaz, da so medianski grafi dvodelni grafi, ki zadoščajo šibki 2-konveksnosti intervalov in štirikotniški lastnosti.
Keywords: matematika, teorija grafov, medianski grafi, delne kocke, semi-medianski grafi, mathematics, graph theory, median graphs, partial cubes, semi median graphs
Published: 10.07.2015; Views: 470; Downloads: 23
URL Link to full text

2.
Median graphs, the remoteness function, periphery transversals, and geodetic number two
Kannan Balakrishnan, Boštjan Brešar, Manoj Changat, Wilfried Imrich, Sandi Klavžar, Matjaž Kovše, Ajitha R. Subhamathi, 2008

Abstract: Periferna transverzala medianskega grafa ▫$G$▫ je vpeljana kot množica vozlišč, ki zadane vse periferije grafa $G$. S pomočjo tega koncepta so na dva različna načina karakterizirani medianski grafi z geodetskim številom 2. To so natanko tisti medianski grafi, ki vsebujejo periferno transverzalo moči 2, kot tudi medianski grafi, za katere obstaja takšen profil, da je funkcija oddaljenosti konstantna na ▫$G$▫. Predstavljen je tudi algoritem, ki v času ▫$O(m log n)$▫ odloči, ali je dani graf z ▫$n$▫ vozlišči in ▫$m$▫ povezavami medianski graf z geodetskim številom 2. Dobljenih je še več nadaljnjih lastnosti funkcije oddaljenosti na hiperkockah in medianskih grafih. Navedenih je tudi nekaj odprtih problemov.
Keywords: medianski graf, medianska množica, funkcija oddaljenosti, geodetsko število, periferna transverzala, median graph, median set, remoteness function, geodetic number, periphery transverzal, hypercube
Published: 10.07.2015; Views: 365; Downloads: 10
URL Link to full text

3.
Weak k-reconstruction of Cartesian products graphs
Wilfried Imrich, Blaž Zmazek, Janez Žerovnik, 2001, published scientific conference contribution abstract

Abstract: Po Ulamovi domnevi je mogoče vsak končen graf ▫$G$▫ rekonstruirati iz množice vseh podgrafov ▫$G$▫ brez ene točke. Znano je, da je mogoče rekonstruirati kartezične produkte. Obravnavan je soroden problem, imenovan šibka rekonstrukcija. Dokazano je, da je mogoče odločiti, ali se da dani graf ▫$H$▫ dobiti iz nekega kartezičnega produkta ▫$g$▫ z odstranitvijo ▫$k$▫ točk, če privzamemo, da ima ▫$G$▫ vsaj ▫$k+1$▫ faktorjev s po ▫$k+1$▫ točkami. V tem rimeru ▫$H$▫ enolično določa ▫$G$▫. Dan je tudi protiprimer za MacAvaneyjevo domnevo.
Keywords: matematika, teorija grafov, kartezični produkt, problem rekonstrukcije, sestavljeni grafi, mathematics, graph theory, reconstruction problem, Cartesian product, composite graphs
Published: 10.07.2015; Views: 357; Downloads: 4
URL Link to full text

4.
Distinguishing Cartesian powers of graphs
Wilfried Imrich, Sandi Klavžar, 2006, original scientific article

Abstract: 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.
Keywords: matematika, teorija grafov, razlikovalno število, grafovski avtomorfizem, produkti grafov, mathematics, graph theory, distingushing number, graph automorphism, products of graphs
Published: 10.07.2015; Views: 310; Downloads: 40
URL Link to full text

5.
Fast recognition of subclasses of almost-median graphs
Wilfried Imrich, Alenka Lipovec, Iztok Peterin, Petra Žigert Pleteršek, 2007, original scientific article

Abstract: In this paper it is shown that a class of almost-median graphs that includes all planar almost-median graphs can be recognized in ▫$O(mlog n)$▫ time, where ▫$n$▫ denotes the number of vertices and ▫$m$▫ the number of edges. Moreover, planar almost-median graphs can be recognized in linear time. As a key auxiliary result we prove that all bipartite outerplanar graphs are isometric subgraphs of the hypercube and that the embedding can be effected in linear time.
Keywords: matematika, teorija grafov, skoraj medianski grafi, algoritem, mathematics, graph theory, almost-median graphs, algorithm, outerplanar graphs
Published: 10.07.2015; Views: 279; Downloads: 7
URL Link to full text

6.
Recognizing Cartesian products in linear time
Wilfried Imrich, Iztok Peterin, 2007, original scientific article

Abstract: We present an algorithm that determines the prime factors of connected graphs with respect to the Cartesian product in linear time and space. This improves a result of Aurenhammer et al. [Cartesian graph factorization at logarithmic cost per edge, Comput. Complexity 2 (1992) 331-349], who compute the prime factors in ▫$O(mlog n)$▫ time, where ▫$m$▫ denotes the number of vertices of ▫$G$▫ and ▫$n$▫ the number of edges. Our algorithm is conceptually simpler. It gains its efficiency by the introduction of edge-labellings.
Keywords: matematika, teorija grafov, kartezični produkt grafov, linearni algoritem, razcep, mathematics, graph theory, Cartesian product graphs, linear algorithm, decomposition
Published: 10.07.2015; Views: 439; Downloads: 77
URL Link to full text

7.
Distinguishing infite graphs
Wilfried Imrich, Sandi Klavžar, Vladimir Ivanovič Trofimov, 2007, original scientific article

Abstract: Razlikovalno število, ▫$D(G)$▫, grafa ▫$G$▫, je najmanjše kardinalno število ▫$aleph$▫, tako da ▫$G$▫ premore označitev z ▫$aleph$▫ oznakami, ki jo ohranja samo trivialni avtomorfizem. Dokažemo, da je razlikovalno število števnega slučajnega grafa enako dva in da imajo drevesom podobni grafi z ne več kot kontinuum vozlišči razlikovalno število enako dva. Določimo tudi razlikovalno število za mnoge razrede neskončnih kartezičnih produktov. Na primer, ▫$D(Q_n) = 2$▫, kjer je ▫$Q_n$▫ neskončna hiperkocka dimenzije ▫$n$▫.
Keywords: matematika, teorija grafov, razlikovalno število, avtomorfizem, neskončni grafi, slučajni graf, kartezični produkt grafov, kardinalna števila, ordinalna števila, mathematics, graph theory, distinguishing number, automorphism, infinite graphs, random graph, Cartesian product of graphs, ordinal numbers, cardinal numbers
Published: 10.07.2015; Views: 231; Downloads: 15
URL Link to full text

8.
Cancellation properties of products of graphs
Wilfried Imrich, Sandi Klavžar, Douglas F. Rall, 2007, short scientific article

Abstract: 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.
Keywords: matematika, teorija grafov, produkti grafov, pravilo krajšanja, enoličnost korenov, mathematics, graph theory, graph products, cancellation property, uniqueness of roots
Published: 10.07.2015; Views: 372; Downloads: 43
URL Link to full text

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

Abstract: 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.
Keywords: teorija grafov, medianski grafi, neskočni grafi, vozliščno-tranzitivni grafi, graph theory, median graphs, infinite graphs, vertex-transitive graphs
Published: 10.07.2015; Views: 334; Downloads: 49
URL Link to full text

10.
The distinguishing number of Cartesian products of complete graphs
Wilfried Imrich, Janja Jerebic, Sandi Klavžar, 2008, published scientific conference contribution

Abstract: 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.
Keywords: matematika, teorija grafov, razlikovalno število, polni grafi, kartezični produkt grafov, mathematics, graph theory, distingushing number, complete graphs, Cartesian product
Published: 10.07.2015; Views: 340; Downloads: 29
URL Link to full text

Search done in 0.24 sec.
Back to top
Logos of partners University of Maribor University of Ljubljana University of Primorska University of Nova Gorica