| | 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 / 31
First pagePrevious page1234Next pageLast page
1.
2.
3.
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: 471; Downloads: 23
URL Link to full text

4.
On cube-free median graphs
Boštjan Brešar, Sandi Klavžar, Riste Škrekovski, 2003

Abstract: Naj bo ▫$G$▫ mediansk graf brez 3-kocke. Pokazano je, da velja ▫$frac{k}{2} ge sqrt{n}-1 ge frac{m}{2sqrt{n}} ge sqrt{s} ge r-1$▫, kjer so ▫$n, m, s, k$▫ in ▫$r$▫ števila točk, povezav, kvadratov, ▫$Theta$▫-razredov in število povezav najmanšega ▫$Theta$▫-razreda grafa ▫$G$▫. Enakosti so dosežene natanko tedaj, ko je ▫$G$▫ kartezični produkt dveh dreves istega reda. Obravnavan je tudi polinom kock medianskih grafov in pokazano je, da lahko ravninske medianske grafe brez 3-kocke prepoznamo v linearnem času.
Keywords: matematika, teorija grafov, medianski graf, kartezični produkt, prepoznavni algoritem, mathematics, graph theory, median graph, cube-free graph, Cartesian product, recognition algoritem
Published: 10.07.2015; Views: 439; Downloads: 10
URL Link to full text

5.
Roots of cube polynomials of median graphs
Boštjan Brešar, Sandi Klavžar, Riste Škrekovski, 2003

Abstract: Polinom kock ▫$c(G,X)$▫ grafa ▫$G$▫ je definiran z ▫$sum_{i ge 0}alpha_i(G)x^i$▫, kjer ▫$alpha_i(G)$▫ označuje število induciranih ▫$i$▫-kock v ▫$G$▫. Naj bo ▫$G$▫ medianski graf. Dokazano je, da je vsaka racionalna ničla polinoma ▫$c(G,x)$▫ oblike ▫$-frac{t+1}{t}$▫ za neko celo število ▫$t>0$▫ in da ima ▫$c(G,x)$▫ vedno realno ničlo na intervalu ▫$[-2,-1)$▫. Nadalje ima ▫$c(G,x)$▫ ▫$p$▫-kratno ničlo natanko tedaj, ko je ▫$G$▫ kartezični produkt ▫$p$▫ dreves istega reda. Grafi acikličnih kubičnih kompleksov so karakterizirani kot grafi za katere velja ▫$c(H,-2)=0$▫ za vsak 2-povezan konveksen podgraf ▫$H$▫.
Keywords: matematika, teorija grafov, polinom kock, koren, medianski graf, kartezični produkt grafov, mathematics, graph theory, cube polynomial, root, median graph, Cartesian product
Published: 10.07.2015; Views: 333; Downloads: 40
URL Link to full text

6.
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

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

9.
10.
Roots of cube polynomials of median graphs
Boštjan Brešar, Sandi Klavžar, Riste Škrekovski, 2006, original scientific article

Abstract: Polinom kock ▫$c(G,x)$▫ grafa ▫$G$▫ je definiran z ▫$sum_{i ge 0}alpha_i(G)x^i$▫, kjer ▫$alpha_i(G)$▫ označuje število induciranih ▫$i$▫-kock v ▫$G$▫. Naj bo ▫$G$▫ medianski graf. Dokazano je, da je vsaka racionalna ničla polinoma ▫$c(G,x)$▫ oblike ▫$-frac{t+1}{t}$▫ za neko celo število ▫$t>0$▫ in da ima ▫$c(G,x)$▫ vedno realno ničlo na intervalu ▫$[-2,-1)$▫. Nadalje ima ▫$c(G,x)$▫ ▫$p$▫-kratno ničlo natanko tedaj, ko je ▫$G$▫ kartezični produkt ▫$p$▫ dreves istega reda. Grafi acikličnih kubičnih kompleksov so karakterizirani kot grafi za katere velja ▫$c(H,-2)=0$▫ za vsak 2-povezan konveksen podgraf ▫$H$▫.
Keywords: matematika, teorija grafov, polinom kock, koren, medianski graf, kartezični produkt grafov, mathematics, graph theory, cube polynomial, root, median graph, Cartesian product
Published: 10.07.2015; Views: 411; Downloads: 46
URL Link to full text

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