| | SLO | ENG | Piškotki in zasebnost

Večja pisava | Manjša pisava

Izpis gradiva

Naslov:On the sharpness of some results relating cuts and crossing numbers
Avtorji:Beaudou, Laurent (Avtor)
Bokal, Drago (Avtor)
Datoteke:.pdf Electronic_Journal_of_Combinatorics_2010_Beaudou,_Bokal_On_the_sharpness_of_some_results_relating_cuts_and_crossing_numbers.pdf (119,22 KB)
 
URL http://www.combinatorics.org/ojs/index.php/eljc/article/view/v17i1r96
 
Jezik:Angleški jezik
Vrsta gradiva:Znanstveno delo (r2)
Tipologija:1.01 - Izvirni znanstveni članek
Organizacija:FNM - Fakulteta za naravoslovje in matematiko
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
Leto izida:2010
Št. strani:str. 1-8
Številčenje:št. 1, Letn. 17
ISSN:1077-8926
UDK:519.17
COBISS_ID:15638361 Povezava se odpre v novem oknu
ISSN pri članku:1077-8926
NUK URN:URN:SI:UM:DK:A59XBR3O
Število ogledov:311
Število prenosov:26
Metapodatki:XML RDF-CHPDL DC-XML DC-RDF
Področja:Ostalo
:
  
Skupna ocena:(0 glasov)
Vaša ocena:Ocenjevanje je dovoljeno samo prijavljenim uporabnikom.
Objavi na:AddThis
AddThis uporablja piškotke, za katere potrebujemo vaše privoljenje.
Uredi privoljenje...

Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše podrobnosti ali sproži prenos.

Gradivo je del revije

Naslov:The Electronic Journal of Combinatorics
Skrajšan naslov:Electron. J. Comb.
Založnik:N.J. Calkin and H.S. Wilf
ISSN:1077-8926
COBISS.SI-ID:6973785 Novo okno

Gradivo je financirano iz projekta

Financer:ARRS - Agencija za raziskovalno dejavnost Republike Slovenije (ARRS)
Številka projekta:P1–0297
Naslov:Teorija grafov

Sekundarni jezik

Jezik:Slovenski jezik
Naslov:O natančnosti nekaterih rezultatov, ki povezujejo prereze in prekrižna števila
Opis: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


Komentarji

Dodaj komentar

Za komentiranje se morate prijaviti.

Komentarji (0)
0 - 0 / 0
 
Ni komentarjev!

Nazaj
Logotipi partnerjev Univerza v Mariboru Univerza v Ljubljani Univerza na Primorskem Univerza v Novi Gorici