| Title: | On the sharpness of some results relating cuts and crossing numbers |
|---|
| Authors: | ID Beaudou, Laurent (Author)
ID Bokal, Drago (Author) |
|---|
| Files: |  Electronic_Journal_of_Combinatorics_2010_Beaudou,_Bokal_On_the_sharpness_of_some_results_relating_cuts_and_crossing_numbers.pdf (119,22 KB)
MD5: C87BD3696801D32B091878645D4F94EC
 http://www.combinatorics.org/ojs/index.php/eljc/article/view/v17i1r96
|
|---|
| Language: | English |
|---|
| Work type: | Scientific work |
|---|
| Typology: | 1.01 - Original Scientific Article |
|---|
| Organization: | FNM - Faculty of Natural Sciences and Mathematics
|
|---|
| Abstract: | 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. |
|---|
| Keywords: | mathematics, graph theory, crossing number, zip product, graph cuts |
|---|
| Publication status: | Published |
|---|
| Publication version: | Version of Record |
|---|
| Submitted for review: | 27.02.2009 |
|---|
| Article acceptance date: | 28.06.2010 |
|---|
| Publication date: | 10.07.2010 |
|---|
| Publisher: | Electronic Journal of Combinatorics |
|---|
| Year of publishing: | 2010 |
|---|
| Number of pages: | str. 1-8 |
|---|
| Numbering: | Letn. 17, št. 1 |
|---|
| PID: | 20.500.12556/DKUM-49391  |
|---|
| ISSN: | 1077-8926 |
|---|
| UDC: | 519.17 |
|---|
| ISSN on article: | 1077-8926 |
|---|
| COBISS.SI-ID: | 15638361 |
|---|
| NUK URN: | URN:SI:UM:DK:A59XBR3O |
|---|
| Publication date in DKUM: | 10.07.2015 |
|---|
| Views: | 1285 |
|---|
| Downloads: | 264 |
|---|
| Metadata: |    |
|---|
| Categories: | Misc.
|
|---|
|
:
|
Copy citation |
|---|
| | | | Average score: | (0 votes) |
|---|
| Your score: | Voting is allowed only for logged in users. |
|---|
| Share: |  |
|---|
Hover the mouse pointer over a document title to show the abstract or click
on the title to get all document metadata. |
