1. Efficient proper embedding of a daisy cubeAleksander Vesel, 2021, izvirni znanstveni članek Opis: For a set ▫$X$▫ of binary words of length ▫$h$▫ the daisy cube ▫$Q_h(X)$▫ is defined as the subgraph of the hypercube ▫$Q_h$▫ induced by the set of all vertices on shortest paths that connect vertices of ▫$X$▫ with the vertex ▫$0^h$▫. A vertex in the intersection of all of these paths is a minimal vertex of a daisy cube. A graph ▫$G$▫ isomorphic to a daisy cube admits several isometric embeddings into a hypercube. We show that an isometric embedding is proper if and only if the label ▫$0^h$▫ is assigned to a minimal vertex of ▫$G$▫. This result allows us to devise an algorithm which finds a proper embedding of a graph isomorphic to a daisy cube into a hypercube in linear time.
Ključne besede: daisy cube, partial cube, isometric embedding, proper embedding
Objavljeno v DKUM: 29.11.2024; Ogledov: 0; Prenosov: 3
 Celotno besedilo (293,91 KB)
Gradivo ima več datotek! Več... |
2. The cut method on hypergraphs for the Wiener indexSandi Klavžar, Gašper Domen Romih, 2023, izvirni znanstveni članek Opis: The cut method has been proved to be extremely useful in chemical graph theory. In this paper the cut method is extended to hypergraphs. More precisely, the method is developed for the Wiener index of ▫$k$▫-uniform partial cube-hypergraphs. The method is applied to cube-hypergraphs and hypertrees. Extensions of the method to hypergraphs arising in chemistry which are not necessary ▫$k$▫-uniform and/or not necessary linear are also developed.
Ključne besede: hypergraphs, Wiener index, cut method, partial cube-hypergraphs, hypertrees, phenylene, Clar structures
Objavljeno v DKUM: 11.04.2024; Ogledov: 230; Prenosov: 10
Celotno besedilo (318,42 KB)
Gradivo ima več datotek! Več... |
3. On [Theta]-graphs of partial cubesSandi Klavžar, Matjaž Kovše, 2007, izvirni znanstveni članek Opis: The ▫$\Theta$▫-graph ▫$\Theta(G)$▫ of a partial cube ▫$G$▫ is the intersection graph of the equivalence classes of the Djokovic-Winkler relation. ▫$\Theta$▫-graphs that are 2-connected, trees, or complete graphs are characterized. In particular, ▫$\Theta(G)$▫ is complete if and only if ▫$G$▫ can be obtained from ▫$K_1$▫ by a sequence of (newly introduced) dense expansions. ▫$\Theta$▫-graphs are also compared with familiar concepts of crossing graphs and ▫$\tau$▫-graphs.
Ključne besede: mathematics, graph theory, intersection graph, partial cube, median graph, expansion theorem, Cartesian product of graphs
Objavljeno v DKUM: 31.03.2017; Ogledov: 1119; Prenosov: 154
Celotno besedilo (150,56 KB)
Gradivo ima več datotek! Več... |
4. Lattice embeddings of treesWilfried 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 v DKUM: 10.07.2015; Ogledov: 1003; Prenosov: 168
 Povezava na celotno besedilo |
5. Partial cubes are distance graphsMelita Gorše Pihler, Janez Žerovnik, 2008, objavljeni znanstveni prispevek na konferenci Opis: 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.
Ključne besede: matematika, teorija grafov, razdaljni graf, delna kocka, hiperkocka, izometrični podgraf, vložitev, mathematics, graph theory, distance graph, partial cube, hypercube, isometric subgraph, embedding
Objavljeno v DKUM: 10.07.2015; Ogledov: 1432; Prenosov: 159
Povezava na celotno besedilo |
6. Tribes of cubic partial cubesSandi Klavžar, Sergey Shpectorov, 2007, izvirni znanstveni članek Opis: 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.
Ključne besede: mathematics, graph theory, partial cube, hypercube, isometric embedding, tribe, algorithm
Objavljeno v DKUM: 10.07.2015; Ogledov: 1088; Prenosov: 182
Celotno besedilo (688,41 KB)
Gradivo ima več datotek! Več... |
7. Characterizing almost-median graphsBoštjan Brešar, 2007, izvirni znanstveni članek Opis: 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.
Ključne besede: matematika, teorija grafov, medianski graf, konveksen cikel, delna kocka, mathematics, graf theory, median graph, convex cycle, partial cube
Objavljeno v DKUM: 10.07.2015; Ogledov: 1281; Prenosov: 104
Povezava na celotno besedilo |
8. A theorem on Wiener-type invariants for isometric subgraphs of hypercubesSandi Klavžar, Ivan Gutman, 2006, izvirni znanstveni članek Opis: Let ▫$d(G,k)$▫ be the number of pairs of vertices of a graph ▫$G$▫ that are at distance ▫$k$▫, ▫$lambda$▫ a real (or complex) number, and ▫$W_lambda(G) = sum_{k ge 1}d(G,k)k^lambda$▫. It is proved that for a partial cube ▫$G$▫, ▫$W_{lambda + 1}(G) = |mathcal{F}| W_lambda(G) - sum_{mathnormal{F} in mathcal{F}} W_lambda(G setminus F)$▫ where ▫$mathcal{F}$▫ is the partition of ▫$E(G)$▫ induced by the Djokovic-Winkler relation ▫$Theta$▫. This result extends a previously known result for trees and implies several relations for distance-based topological indices.
Ključne besede: mathematics, graph theory, graph distance, hypercube, partial cube, Wiener number, hyper-Wiener indeks
Objavljeno v DKUM: 10.07.2015; Ogledov: 1388; Prenosov: 127
Povezava na celotno besedilo |
9. Partial cubes are distance graphsMelita Gorše Pihler, Janez Žerovnik, 2005 Opis: 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.
Ključne besede: matematika, teorija grafov, razdaljni graf, delna kocka, hiperkocka, izometrični podgraf, vložitev, mathematics, graph theory, distance graph, partial cube, hypercube, isometric subgraph, embedding
Objavljeno v DKUM: 10.07.2015; Ogledov: 1435; Prenosov: 112
Povezava na celotno besedilo |
10. On cubic and edge-critical isometric subgraphs of hypercubesC. Paul Bonnington, Sandi Klavžar, Alenka Lipovec, 2002 Opis: 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.
Ključne besede: matematika, teorija grafov, delna kocka, hiperkocka, kubični graf, računalniško iskanje, mathematics, graph theory, partial cube, hypercube, cubic graph, computer searching
Objavljeno v DKUM: 10.07.2015; Ogledov: 1207; Prenosov: 39
Povezava na celotno besedilo |
