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


1 - 10 / 31
First pagePrevious page1234Next pageLast page
Tree-like isometric subgraphs of hypercubes
Boštjan Brešar, Wilfried Imrich, Sandi Klavžar, 2003, original scientific article

Abstract: Tree-like isometric subgraphs of hypercubes, or tree-like partial cubes as we call them, are a generalization of median graphs. Just as median graphs they capture numerous properties of trees, but may contain larger classes of graphs that may be easier to recognize than the class of median graphs. We investigate the structure of tree-like partial cubes, characterize them, and provide examples of similarities with trees and median graphs. For instance, we show that the cube graph of tree-like partial cube is dismantlable. This in particular implies that every tree-like partial cube ▫$G$▫ contains a cube that is invariant under every automorphism of ▫$G$▫. We also show that weak retractions preserve tree-like partial cubes, which in turn implies that every contraction of a tree-like partial cube fixes a cube. The paper ends with several Frucht-type results and a list of open problems.
Keywords: mathematics, graph theory, Isometric embeddings, partial cubes, expansion procedures, trees, median graphs, graph automorphisms, automorphism groups, dismantlable graphs
Published: 31.03.2017; Views: 815; Downloads: 291
.pdf Full text (135,80 KB)
This document has many files! More...

The periphery graph of a median graph
Boštjan Brešar, Manoj Changat, Ajitha R. Subhamathi, Aleksandra Tepeh, 2010, original scientific article

Abstract: The periphery graph of a median graph is the intersection graph of its peripheral subgraphs. We show that every graph without a universal vertex can be realized as the periphery graph of a median graph. We characterize those median graphs whose periphery graph is the join of two graphs and show that they are precisely Cartesian products of median graphs. Path-like median graphs are introduced as the graphs whose periphery graph has independence number 2, and it is proved that there are path-like median graphs with arbitrarily large geodetic number. Peripheral expansion with respect to periphery graph is also considered, and connections with the concept of crossing graph are established.
Keywords: mathematics, graph theory, median graph, Cartesian product, geodesic, periphery, peripheral expansion
Published: 31.03.2017; Views: 845; Downloads: 308
.pdf Full text (145,86 KB)
This document has many files! More...

On [Theta]-graphs of partial cubes
Sandi Klavžar, Matjaž Kovše, 2007, original scientific article

Abstract: 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.
Keywords: mathematics, graph theory, intersection graph, partial cube, median graph, expansion theorem, Cartesian product of graphs
Published: 31.03.2017; Views: 523; Downloads: 66
.pdf Full text (150,56 KB)
This document has many files! More...

Median and quasi-median direct products of graphs
Boštjan Brešar, Pranava Jha, Sandi Klavžar, Blaž Zmazek, 2005, original scientific article

Abstract: Median graphs are characterized among direct products of graphs on at least three vertices. Beside some trivial cases, it is shown that one component of ▫$G \times P_3$▫ is median if and only if ▫$G$▫ is a tree in that the distance between any two vertices of degree at least 3 is even. In addition, some partial results considering median graphs of the form ▫$G \times K_2$▫ are proved, and it is shown that the only nonbipartite quasi-median direct product is ▫$K_3 \times K_3$▫.
Keywords: mathematics, graph theory, median graph, direct product, quasi-median graph, isometric embeddings, convexity
Published: 31.03.2017; Views: 578; Downloads: 247
.pdf Full text (174,14 KB)
This document has many files! More...

Arboreal structure and regular graphs of median-like classes
Boštjan Brešar, 2003, original scientific article

Abstract: We consider classes of graphs that enjoy the following properties: they are closed for gated subgraphs, gated amalgamation and Cartesian products, and for any gated subgraph the inverse of gate function maps vertices to gated subsets. We prove that any graph of such a class contains a peripheral subgraph which is a Cartesian product of two graphs: a gated subgraph and a prime graph minus a vertex. Therefore, these graphs admit a peripheral elimination procedure which is a generalization of analogous procedure in median graphs. We characterize regular graphs of these classes whenever they enjoy an additional properties. As a corollary we derive that regular weakly median graphs are precisely Cartesian products in which each factor is a complete graph or a hyperoctahedron.
Keywords: mathematics, graph theory, median graph, tree, gatedness, amalgam, periphery, regular graph
Published: 31.03.2017; Views: 500; Downloads: 285
.pdf Full text (127,35 KB)
This document has many files! More...

Retracts of products of chordal graphs
Boštjan Brešar, Jérémie Chalopin, Victor Chepoi, Matjaž Kovše, Arnaud Labourel, Yann Vaxès, 2010

Abstract: We characterize the graphs ▫$G$▫ that are retracts of Cartesian products of chordal graphs. We show that they are exactly the weakly modular graphs that do not contain ▫$K_{2;3}$▫, ▫$k$▫-wheels ▫$W_k$▫, and ▫$k$▫-wheels minus one spoke T$W_k^- ; (k ge 4)$T as induced subgraphs. We also show that these graphs ▫$G$▫ are exactly the cage-amalgamation graphs introduced by Brešar and Tepeh Horvat (2009); this solves the open question raised by these authors. Finally, we prove that replacing all products of cliques of $G$ by products of "solid" simplices, we obtain a polyhedral cell complex which, endowed with an intrinsic Euclidean metric, is a CAT(0) space. This generalizes similar results about median graphs as retracts of hypercubes (products of edges) and median graphs as 1-skeletons of CAT(0) cubical complexes.
Keywords: teorija grafov, graf, retrakt, zastražena amalgamacija, tetiven graf, kartezični produkt grafov, medianski graf, graph theory, graph, retract, gated amalgamation, chordal graph, Cartesian product of graphs, median graph
Published: 10.07.2015; Views: 559; Downloads: 81
URL Link to full text

Geodetic sets in graphs
Boštjan Brešar, Matjaž Kovše, Aleksandra Tepeh, 2011, independent scientific component part or a chapter in a monograph

Abstract: Na kratko so povzeti rezultati o geodetskih množicah v grafih. Po pregledu rezultatov iz prejšnjih raziskav se posvetimo geodetskemu številu in sorodnim invariantam v grafih. Podrobno so obravnavane geodetske množice kartezičnih produktov grafov in geodetske množice v medianskih grafih. Predstavljen je tudi algoritmični vidik in povezava z nekaterimi ostalimi koncepti iz teorije konveksnih in intervalskih struktur v grafih.
Keywords: matematika, teorija grafov, geodetsko število, geodetska množica, kartezični produkt, medianski graf, mejna množica, mathematics, graph theory, geodetic number, geodetic set, Cartesian product, median graph, boundary set
Published: 10.07.2015; Views: 373; Downloads: 22
URL Link to full text

Simultaneous embeddings of graphs as median and antimedian subgraphs
Kannan Balakrishnan, Boštjan Brešar, Manoj Changat, Sandi Klavžar, Matjaž Kovše, Ajitha R. Subhamathi, 2010, original scientific article

Abstract: Razdalja ▫$D_G(v)$▫ vozlišča ▫$v$▫ v grafu ▫$G$▫ je vsota razdalj med ▫$v$▫ in vsemi drugimi vozlišči grafa ▫$G$▫. Množica vozlišč grafa ▫$G$▫ z maksimalno (minimalno) razdaljo je antimedianska (medianska) množica grafa ▫$G$▫. Dokazano je, da za poljubna grafa ▫$G$▫ in ▫$J$▫ ter za poljubno naravno število ▫$r ge 2$▫ obstaja povezani graf ▫$H$▫, tako da je ▫$G$▫ antimedianski in ▫$J$▫ medianski podgraf grafa ▫$H$▫ ter da pri tem velja ▫$d_H(G,J) = r$▫. V primeru, ko sta oba ▫$G$▫ in ▫$J$▫ povezana, lahko dodatno naredimo, da sta ▫$G$▫ in ▫$J$▫ konveksna podgrafa v ▫$H$▫.
Keywords: matematika, teorija grafov, problemi razmeščanja, medianske množice, antimedianske množice, konveksni podgrafi, mathematics, graph theory, facility location problems, median sets, antimedian sets, convex subgraphs
Published: 10.07.2015; Views: 603; Downloads: 79
URL Link to full text

On the remoteness function in median graphs
Kannan Balakrishnan, Boštjan Brešar, Manoj Changat, Wilfried Imrich, Sandi Klavžar, Matjaž Kovše, Ajitha R. Subhamathi, 2009, original scientific article

Abstract: Profil grafa ▫$G$▫ je poljubna neprazna multimnožica vozlišč iz ▫$G$▫. Pripadajoča funkcija oddaljenosti priredi vsakemu vozlišču iz ▫$V(G)$▫ vsoto razdalj do vozlišč iz profila. Najprej so dobljene nekatere uporabne lastnosti funkcije oddaljenosti na hiperkockah, nato pa je funkcija oddaljenosti obravnavana na poljubnih medianskih grafih glede na njihove izometrične vložitve v hiperkocke. V posebnem je najdena povezava med vozlišči medianskega grafa ▫$G$▫, katerega funkcija oddaljenosti je največja (antimedianska množica v ▫$G$▫), z antimediansko množico pripadajoče hiperkocke. Medtem ko je za lihe profile antimedianska množica neodvisna množica, ki leži na strogem robu medianskega grafa, obstajajo medianski grafi, v katerih določeni sodi profili porajajo konstantno funkcijo oddaljenosti. Take medianske grafe karakteriziramo na dva načina: kot grafe, katerih periferna transverzala je 2, in kot grafe z geodetskim številom 2. Nazadnje predstavimo algoritem, ki za dani graf ▫$G$▫ z ▫$n$▫ vozlišči in ▫$m$▫ povezavami v času ▫$O(m log n)$▫ odloči, ali je ▫$G$▫ medianski graf z geodetskim številom 2.
Keywords: hiperkocka, 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: 656; Downloads: 87
URL Link to full text

Cube intersection concepts in median graphs
Boštjan Brešar, Tadeja Kraner Šumenjak, 2009, original scientific article

Abstract: Obravnavamo različne razrede presečnih grafov maksimalnih hiperkock medianskih grafov. Za medianski graf ▫$G$▫ in celo število ▫$k ge 0$▫ je presečni graf ▫${mathcal{Q}}_k(G)$▫ definiran kot tisti graf, katerega vozlišča so maksimalne hiperkocke (z ozirom na inkluzijo) grafa ▫$G$▫ in sta dve vozlišči ▫$H_x$▫ in ▫$H_y$▫ v njem sosednji tedaj, ko presek ▫$H_x cap H_y$▫ vsebuje podgraf izomorfen ▫$Q_k$▫. V članku predstavimo karakterizacije kličnih grafov z uporabo omenjenih presečnih konceptov, ko je ▫$k>0$▫. Vpeljemo tudi t.i. maksimalno 2-presečni graf maksimalnih hiperkock medianskega grafa ▫$G$▫, ki ga označimo z ▫${mathcal{Q}}_{m2}(G)$▫ in predstavlja tisti graf, katerega vozlišča somaksimalne hiperkocke grafa ▫$G$▫, dve vozlišči v njem pa sta sosednji, če presek pripadajočih hiperkock ni strogo vsebovan v kakem preseku dveh maksimalnih hiperkock. Dokažemo, da je graf ▫$H$▫ brez induciranih diamantov, če in samo če obstaja takšen medianski graf ▫$G$▫, da je ▫$H$▫ izomorfen ▫${mathcal{Q}}_{m2}(G)$▫. Obravnavamo tudi konvergenco medianskega grafa h grafu na enem vozlišču glede na vse vpeljane operacije.
Keywords: matematika, teorija grafov, kartezični produkt, medianski graf, graf kock, presečni graf, konveksnost, mathematics, graph theory, Cartesian product, median graph, cube graph, intersection graph, convexity
Published: 10.07.2015; Views: 643; Downloads: 85
URL Link to full text

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