| | 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: 556; Downloads: 24
URL Link to full text

2.
3.
The cube polynomial and its derivatives: the case of median graphs
Boštjan Brešar, Sandi Klavžar, Riste Škrekovski, 2003, original scientific article

Abstract: Naj bo ▫$alpha_i(G)$▫ število induciranih ▫$i$▫-kock grafa ▫$G$▫. Tedaj je polinom kock ▫$c(G,x)$▫ grafa ▫$G$▫ definiran z ▫$sum_{i ge 0} alpha_i (G) x_i$▫. Pokazano je, da je vsaka funkcija ▫$f$▫ z dvemi predpisanimi naravnimi lastnostmi do faktorja ▫$f(Q_0,x)$▫ enaka polinomu kock. Vpeljan je tudi odvod ▫$partial G$▫ medianskega grafa ▫$G$▫. Dokazano je, da je polinom kock edina funkcija ▫$f$▫ z lastnostjo ▫$f'(G,z) = f(partial G,x)$▫, če je le ▫$f(G,0) = |V(G)|$▫. Dokazanih je tudi več relacij za medianske grafe, ki posplošujejo prej znane rezultate. Na primer, za vsak ▫$s ge 0$▫ velja ▫$c^{(s)}(G, x+1) = sum_{i ge s} frac{c^{(s)}(G,x)}{(i-s)!}$▫.
Keywords: matematika, teorija grafov, polinom kock, odvod grafa, medianski grafi, mathematics, graph theory, cube polynomials, graph derivation, median graphs
Published: 10.07.2015; Views: 360; Downloads: 17
URL Link to full text

4.
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: 327; Downloads: 8
URL Link to full text

6.
Partial cubes and their [tau]-graphs
Sandi Klavžar, Matjaž Kovše, 2007, original scientific article

Abstract: Za delno kocko ▫$G$▫ ima ▫$tau$▫-graph ▫$G^tau$▫ ekvivalenčne razrede Djokovic-Winklerjeve relacije kot vozlišča, pri čemer sta razreda ▫$E$▫ in ▫$F$▫ sosednja, če neki povezavi ▫$e in E$▫ in ▫$f in F$▫ inducirata konveksno pot ▫$P_3$▫. Dokazano je, da za vsak graf $G$ obstaja medianski graf ▫$M$▫, tako da velja ▫$G = M^tau$▫, da je ▫$G^tau$▫ povezan natanko tedaj, ko je ▫$G$▫ pragraf glede na kartezični produkt grafov in da je ▫$tau$▫-graf medianskega grafa ▫$G$▫ brez ▫$K_n$▫ natanko tedaj, ko ▫$G$▫ ne vsebuje konveksnega ▫$K_{1,n}$▫.
Keywords: matematika, teorija grafov, delne kocke, medianski grafi, kartezični produkt grafov, mathematics, graf theory, partial cubes, median graphs, Cartesian product graphs
Published: 10.07.2015; Views: 361; Downloads: 14
URL Link to full text

7.
Crossing graphs of fiber-complemented graphs
Boštjan Brešar, Aleksandra Tepeh, 2008, original scientific article

Abstract: Grafi zastraženih inverzov tvorijo obsežno nedvodelno posplošitev medianskih grafov. Z uporabo določenega naravnega barvanja povezav, ki je porojeno z relacijo vzporednosti med predvlakni grafov zastraženih inverzov, vpeljemo križni graf grafa zastraženega inverza ▫$G$▫ kot graf, katerega vozlišča so barve, dve barvi pa sta sosednji, če se križata na kakem induciranem 4-ciklu v grafu ▫$G$▫. V članku pokažemo, da je graf zastraženega inverza 2-povezan natanko tedaj, ko je njegov križni graf povezan. Karakteriziramo tiste grafe zastraženih inverzov, ki imajo poln križni graf pa tudi tiste s tetivnim križnim grafom.
Keywords: matematika, teorija grafov, medianski grafi, zastražene množice, predvlakna, kartezični produkt grafov, ekspanzija, mathematics, graph theory, median graphs, gated sets, prefibers, kartezični produkti, expansion
Published: 10.07.2015; Views: 490; Downloads: 60
URL Link to full text

8.
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: 426; Downloads: 60
URL Link to full text

9.
On the geodetic number of median graphs
Boštjan Brešar, Aleksandra Tepeh, 2008, original scientific article

Abstract: Množica vozlišč ▫$S$▫ v grafu se imenuje geodetska množica, če vsako vozlišče tega grafa leži na kaki najkrajši poti med dvema vozliščema iz množice ▫$S$▫. V članku raziskujemo najmanjše geodetske množice medianskih grafov z ozirom na operacijo periferne ekspanzije. Spotoma obravnavamo geodetske množice medianskih prizem in karakteriziramo medianske grafe, ki imajo geodetsko množico velikosti 2.
Keywords: matematika, teorija grafov, medianski grafi, geodetsko število, geodetska množica, kartezični produkt grafov, ekspanzija, mathematics, graph theory, median graphs, geodetic number, geodetic set, Cartesian product, geodesic, expansion
Published: 10.07.2015; Views: 383; Downloads: 50
URL Link to full text

10.
Cage-amalgamation graphs, a common generalization of chordal and median graphs
Boštjan Brešar, Aleksandra Tepeh, 2009, original scientific article

Abstract: V članku je vpeljan in na različne načine okarakteriziran nov razred grafov, imenovan grafi amalgamov kletk, ki je vsebovan v šibko modularnih grafih in grafih zastraženih inverzov in ki vsebuje tako medianske kot tetivne grafe. Vpeljemo tudi variacijo Hammingovega polinoma in jo uporabimo pri izpeljavi dveh enakosti drevesnega tipa za ta razred grafov, ki sta bili prej znani za tetivne in medianske grafe. Prva enakost je ▫$sum_{ige 0}, (-1)^{i}, rho_i(G)=1$▫, kjer je ▫$rho_i(G)$▫ število ▫$i$▫-regularnih Hammingovih podgrafov v grafu amalgamov kletk ▫$G$▫.
Keywords: matematika, teorija grafov, medianski grafi, tetivni grafi, konveksnost, amalgamacija, enakosti drevesnega tipa, mathematics, graph theory, median graphs, chordal graphs, convexity, amalgamation, tree-like equalities
Published: 10.07.2015; Views: 283; Downloads: 51
URL Link to full text

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