| | SLO | ENG | Piškotki in zasebnost

Večja pisava | Manjša pisava

Iskanje po katalogu digitalne knjižnice Pomoč

Iskalni niz: išči po
išči po
išči po
išči po
* po starem in bolonjskem študiju

Opcije:
  Ponastavi


1 - 8 / 8
Na začetekNa prejšnjo stran1Na naslednjo stranNa konec
1.
The minor crossing number of graphs with an excluded minor
Drago Bokal, Gašper Fijavž, David Richard Wood, 2008, izvirni znanstveni članek

Opis: The minor crossing number of a graph ▫$G$▫ is the minimum crossing number of a graph that contains ▫$G$▫ as a minor. It is proved that for every graph ▫$H$▫ there is a constant ▫$c$▫, such that every graph ▫$G$▫ with no ▫$H$▫-minor has minor crossing number at most ▫$c|V(G)|$▫.
Ključne besede: mathematics, graph theory, graph minor, excluded minor, crossing number, minor crossing number
Objavljeno: 10.07.2015; Ogledov: 270; Prenosov: 42
.pdf Celotno besedilo (189,15 KB)
Gradivo ima več datotek! Več...

2.
On the sharpness of some results relating cuts and crossing numbers
Laurent Beaudou, Drago Bokal, 2010, izvirni znanstveni članek

Opis: It is already known that for very small edge cuts in graphs, the crossing number of the graph is at least the sum of the crossing number of (slightly augmented) components resulting from the cut. Under stronger connectivity condition in each cut component that was formalized as a graph operation called zip product, a similar result was obtained for edge cuts of any size, and a natural question was asked, whether this stronger condition is necessary. In this paper, we prove that the relaxed condition is not sufficient when the size of the cut is at least four, and we prove that the gap can grow quadratically with the cut size.
Ključne besede: mathematics, graph theory, crossing number, zip product, graph cuts
Objavljeno: 10.07.2015; Ogledov: 312; Prenosov: 26
.pdf Celotno besedilo (119,22 KB)
Gradivo ima več datotek! Več...

3.
Crossing numbers of Sierpiński-like graphs
Sandi Klavžar, Bojan Mohar, 2005, izvirni znanstveni članek

Opis: Obravnavano je prekrižno število grafov Sierpińskega ▫$S(n,k)$▫ in njihovih regularizacij ▫$S^+(n,k)$▫ in ▫$S^{++}(n,k)$▫. Predstavljene so eksplicitne risbe teh grafov, ki so optimalne za ▫$S^+(n,k)$▫ in ▫$S^{++}(n,k)$▫ za vse ▫$n ge 1$▫ in ▫$k ge 1$▫. To sta prvi netrivialni družini grafov "fraktalnega" tipa, za katere je poznano prekrižno število.
Ključne besede: matematika, teorija grafov, risanje grafov, prekrižno število, grafi Sierpińskega, avtomorfizmi grafov, mathematics, graf theory, graph drawing, crossing number, Sierpiński graphs, graph automorphism
Objavljeno: 10.07.2015; Ogledov: 397; Prenosov: 35
URL Povezava na celotno besedilo

4.
General lower bounds for the minor crossing number of graphs
Drago Bokal, Éva Czabarka, László Székely, Imrich Vrt'o, 2008

Opis: There are three general lower bound techniques for the crossing numbers of graphs: the Crossing Lemma, the bisection method and the embedding method. Inthis contribution, we present their adaptations to the minor crossing number. Using the adapted bounds, we improve on the known bounds on the minor crossing number of hypercubes. We also point out relations of the minor crossing number to string graphs.
Ključne besede: teorija grafov, prekrižno število, minor, hiper kocke, graph theory, minor crossing number, graph minor, string graphs, hypercubes
Objavljeno: 10.07.2015; Ogledov: 266; Prenosov: 39
URL Povezava na celotno besedilo

5.
6.
Infinite families of crossing-critical graphs with prescribed average degree and crossing number
Drago Bokal, 2010, izvirni znanstveni članek

Opis: Širan constructed infinite families of ▫$k$▫-crossing-critical graphs for every ▫$k ge 3$▫ and Kochol constructed such families of simple graphs for every ▫$k ge 2$▫. Richter and Thomassen argued that, for any given ▫$k ge 1$▫ and ▫$r ge 6$▫, there are only finitely many simple ▫$k$▫-crossing-critical graphs with minimum degree ▫$r$▫. Salazar observed that the same argument implies such a conclusion for simple ▫$k$▫-crossing-critical graphs of prescribed average degree ▫$r > 6$▫. He established existence of infinite families of simple ▫$k$▫-crossing-critical graphs with any prescribed rational average degree ▫$r in [4,6)$▫ for infinitely many ▫$k$▫ and asked about their existence for ▫$r in (3,4)$▫. The question was partially settled by Pinontoan and Richter, who answered it positively for ▫$r in (3frac{1}{2},4)$▫. The present contribution uses two new constructions of crossing critical simple graphs along with the one developed by Pinontoan and Richter to unify these results and to answer Salazar's question by the following statement: for every rational number ▫$r in (3,6)$▫ there exists an integer ▫$N_r$▫, such that, for any ▫$k > N_r$▫, there exists an infinite family of simple 3-connected crossing-critical graphs with average degree ▫$r$▫ and crossing number ▫$k$▫. Moreover, a universal lower bound on ▫$k$▫ applies for rational numbers in any closed interval ▫$I subset (3,6)$▫.
Ključne besede: matematika, teorija grafov, prekrižno število, kritičen graf, prekrižno-kritičen graf, povprečna stopnja, mathematics, graph theory, crossing number, critical graph, crossing-critical graph, average degree, graph
Objavljeno: 10.07.2015; Ogledov: 363; Prenosov: 54
URL Povezava na celotno besedilo

7.
General lower bounds for the minor crossing number of graphs
Drago Bokal, Éva Czabarka, László Székely, Imrich Vrt'o, 2010, izvirni znanstveni članek

Opis: Obstajajo tri splošne spodnje meje za minorsko prekrižno število grafov: prekrižna lema, metoda z bisekcijo in metoda z vložitvami. V tem prispevku predstavimo njihove prilagoditve za minorsko prekrižno število grafov. S tako pridobljenimi spodnjimi mejami izboljšamo znane rezultate za minorsko prekrižno število hiperkock. Poleg navedenih rezultatov predstavimo tudi povezavo med minorskim prekrižnim številom in grafi, predstavljivimi s krivuljami (string-graphs).
Ključne besede: teorija grafov, minorsko prekrižno število, grafovski minor, krivuljski grafi, hiper kocke, graph theory, minor crossing number, graph minor, string graphs, hypercubes
Objavljeno: 10.07.2015; Ogledov: 319; Prenosov: 60
URL Povezava na celotno besedilo

8.
Crossing number additivity over edge cuts
Drago Bokal, Markus Chimani, Jesús Leanõs, 2013, izvirni znanstveni članek

Opis: Consider a graph ▫$G$▫ with a minimal edge cut ▫$F$▫ and let ▫$G_1$▫, ▫$G_2$▫ be the two (augmented) components of ▫$G-F$▫. A long-open question asks under which conditions the crossing number of ▫$G$▫ is (greater than or) equal to the sum ofcthe crossing numbers of ▫$G_1$▫ and ▫$G_2$▫ - which would allow us to consider those graphs separately. It is known that crossing number is additive for ▫$|F| in {0,1,2}$▫ and that there exist graphs violating this property with ▫$|F| ge 4$▫. In this paper, we show that crossing number is additive for ▫$|F|=3$▫, thus closing the final gap in the question. The techniques generalize to show that minor crossing number is additive over edge cuts of arbitrary size, as well as to provide bounds for crossing number additivity in arbitrary surfaces. We point out several applications to exact crossing number computation and crossing-critical graphs, as well as provide a very general lower bound for the minor crossing number of the Cartesian product of an arbitrary graph with a tree.
Ključne besede: matematika, teorija grafov, prekrižno število, minor, mathematics, graph theory, crossing number, minor
Objavljeno: 10.07.2015; Ogledov: 423; Prenosov: 43
URL Povezava na celotno besedilo

Iskanje izvedeno v 0.21 sek.
Na vrh
Logotipi partnerjev Univerza v Mariboru Univerza v Ljubljani Univerza na Primorskem Univerza v Novi Gorici