Laurent Beaudou (Avtor), Drago Bokal (Avtor)

Povzetek

Znano je, da je za majhne povezavne prereze prekrižno število grafa večje ali enako vsoti prekrižnih števil nekoliko dopolnjenih komponent, ki nastanejo ob prerezu. Ob močnejših predpostavkah povezanosti vsake od komponent, ki je bilo formalizirano kot grafovska operacija 'šiv', pa lahko podoben rezultat pokažemo za povezavne prereze poljubne velikosti. Zastavi se naravno vprašanje, ali je ta pogoj potreben. V tem prispevku pokažemo, da šibkejše zahteve za povezanost komponent ne zadoščajo, če prerez vsebuje vsaj štiri povezave. Razlika med vsoto prekrižnih števil komponent in skupnega grafa lahko narašča kvadratično z velikostjo prereza.

Ključne besede

matematika;teorija grafov;prekrižno število;šiv grafov;prerez v grafih;mathematics;graph theory;crossing number;zip product;graph cuts;

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: 15638361 Povezava se bo odprla v novem oknu
ISSN: 1077-8926
Št. ogledov: 18
Št. prenosov: 13
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: O natančnosti nekaterih rezultatov, ki povezujejo prereze in prekrižna števila
Sekundarni povzetek: 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.
Sekundarne ključne besede: matematika;teorija grafov;prekrižno število;šiv grafov;prerez v grafih;
URN: URN:SI:UM:
Vrsta dela (COBISS): Delo ni kategorizirano
Strani: R96 (8 str.)
Letnik: ǂVol. ǂ17
Zvezek: ǂno. ǂ1
Čas izdaje: 2010
ID: 68561