Drago Bokal (Avtor), Éva Czabarka (Avtor), László Székely (Avtor), Imrich Vrt'o (Avtor)

Povzetek

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;

Podatki

Jezik: Angleški jezik
Leto izida:
Tipologija: 1.01 - Izvirni znanstveni članek
Organizacija: UM FNM - Fakulteta za naravoslovje in matematiko
UDK: 519.17
COBISS: 15636057 Povezava se bo odprla v novem oknu
ISSN: 0179-5376
Št. ogledov: 29
Št. prenosov: 3
Ocena: 0 (0 glasov)
Metapodatki: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Ostali podatki

Sekundarni jezik: Neznan jezik
Sekundarni naslov: Splošne spodnje meje za minorsko prekrižno število grafov
Sekundarni povzetek: There are three general lower bound techniques for the crossing numbers of graphs: the Crossing Lemma, the bisection method and the embedding method. In this 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.
URN: URN:SI:UM:
Vrsta dela (COBISS): Delo ni kategorizirano
Strani: str. 463-483
Letnik: Vol. 44
Zvezek: no. 2
Čas izdaje: 2010
ID: 1475178