20.500.12556/DKUM-49391 On the sharpness of some results relating cuts and crossing numbers O natančnosti nekaterih rezultatov, ki povezujejo prereze in prekrižna števila 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. 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. mathematics graph theory crossing number zip product graph cuts matematika teorija grafov prekrižno število šiv grafov prerez v grafih true true true Electronic Journal of Combinatorics Angleški jezik Slovenski jezik Znanstveno delo 2015-07-10 12:02:23 2015-07-10 12:02:24 2025-09-02 13:40:01 2022-03-30 03:06:42 2010 0 0 str. 1-8 št. 1 Letn. 17 2010 0000-00-00 Zaloznikova Objavljeno NiDoloceno 2009-02-27 2010-06-28 2010-07-10 1077-8926 519.17 6973785 15638361 1077-8926 URN:SI:UM:DK:A59XBR3O Electronic_Journal_of_Combinatorics_2010_Beaudou,_Bokal_On_the_sharpness_of_some_results_relating_cuts_and_crossing_numbers.pdf Electronic_Journal_of_Combinatorics_2010_Beaudou,_Bokal_On_the_sharpness_of_some_results_relating_cuts_and_crossing_numbers.pdf 1 C87BD3696801D32B091878645D4F94EC a3800a81c206eb627dac15c8cfaa8693ebbd861381239b74101a03717225c71f 8246649d-7c0e-11eb-bb7a-00155d0001ca https://dk.um.si/Dokument.php?lang=slv&id=115232 http://www.combinatorics.org/ojs/index.php/eljc/article/view/v17i1r96 1 https://dk.um.si/Dokument.php?lang=slv&id=73950 Fakulteta za naravoslovje in matematiko 0 0 0