1. On cubic and edge-critical isometric subgraphs of hypercubesC. Paul Bonnington, Sandi Klavžar, Alenka Lipovec, 2002 Abstract: Predstavljene so vse kubične delne kocke do 30 točk in vse po povezavah kritične delne kocke do 14 točk. Seznama sta bila potrjena z računalniškim iskanjem. Konstruirane so tudi netrivialne kubične delne kocke na 36, 42 in 48 točkah.
Keywords: matematika, teorija grafov, delna kocka, hiperkocka, kubični graf, računalniško iskanje, mathematics, graph theory, partial cube, hypercube, cubic graph, computer searching
Published: 10.07.2015; Views: 254; Downloads: 6
 Link to full text |
2. On cube-free median graphsBoš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: 435; Downloads: 10
Link to full text |
3. Roots of cube polynomials of median graphsBoš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: 330; Downloads: 39
Link to full text |
4. Partial cubes are distance graphsMelita Gorše Pihler, Janez Žerovnik, 2005 Abstract: Chatrand, Kubicki in Schultz [Aequationes Math. 55 (1998) 129-145] so postavili domnevo, da so vsi dvodelni grafi razdaljni grafi. V tem članku pokažemo, da so vsi grafi podmnožice dvodelnih grafov, in sicer delne kocke, razdaljni grafi.
Keywords: matematika, teorija grafov, razdaljni graf, delna kocka, hiperkocka, izometrični podgraf, vložitev, mathematics, graph theory, distance graph, partial cube, hypercube, isometric subgraph, embedding
Published: 10.07.2015; Views: 356; Downloads: 59
Link to full text |
5. The cube polynomial and its derivatives: the case of median graphsBoš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
Link to full text |
6. Roots of cube polynomials of median graphsBoš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: 408; Downloads: 45
Link to full text |
7. A theorem on Wiener-type invariants for isometric subgraphs of hypercubesSandi Klavžar, Ivan Gutman, 2006, original scientific article Abstract: Naj bo ▫$d(G,k)$▫ število parov točk grafa ▫$G$▫, ki so na razdalji ▫$k$▫, naj bo ▫$lambda$▫ realno (ali kompleksno) število in naj bo ▫$W_lambda(G) =sum_{k ge 1}d(G,k)k^lambda$▫. Dokazano je, da za delno kocko ▫$G$▫ velja ▫$W_{lambda + 1}(G) = |mathcal{F}| W_lambda(G) - sum_{mathnormal{F} in mathcal{F}} W_lambda(G setminus F)$▫, kjer je ▫$mathcal{F}$▫ particija ▫$E(G)$▫, ki jo inducira Djokovic-Winklerjeva relacija ▫$Theta$▫. Ta rezultat razširja prej znani rezultat za drevesa in implicira različne relacije za topološke indekse, ki temeljijo na razdaljah.
Keywords: matematika, teorija grafov, grafovska razdalja, hiperkocka, delna kocka, Wienerjevo število, hiper-Wienerjev indeks, mathematics, graph theory, graph distance, hypercube, partial cube, Wiener number, hyper-Wiener indeks
Published: 10.07.2015; Views: 459; Downloads: 42
Link to full text |
8. On cube-free median graphsBoštjan Brešar, Sandi Klavžar, Riste Škrekovski, 2007, original scientific article 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: 366; Downloads: 11
Link to full text |
9. Characterizing almost-median graphsBoštjan Brešar, 2007, original scientific article Abstract: Skoraj medianski grafi in semi-medianski grafi sta dve naravni posplošitvi dobro znanega razreda medianskih grafov. V članku dokažemo, da je semi-medianski graf skoraj medianski, če in samo če ne vsebuje konveksnega cikla dolžine večje kot štiri.
Keywords: matematika, teorija grafov, medianski graf, konveksen cikel, delna kocka, mathematics, graf theory, median graph, convex cycle, partial cube
Published: 10.07.2015; Views: 356; Downloads: 55
Link to full text |
10. Tribes of cubic partial cubesSandi Klavžar, Sergey Shpectorov, 2007, original scientific article Abstract: Partial cubes are graphs isometrically embeddable into hypercubes. Three infinite families and a few sporadic examples of cubic partial cubes are known. The concept of a tribe is introduced as means to systematize the known examples and establish relations among them. Efficient methods of computation of tribes are developed and several concrete tribes, that include known, as well as new cubic partial cubes, are computed by hand and with the use of a computer.
Keywords: mathematics, graph theory, partial cube, hypercube, isometric embedding, tribe, algorithm
Published: 10.07.2015; Views: 280; Downloads: 69
 Full text (688,41 KB)
This document has many files! More...
|
