On the sharpness of some results relating cuts and crossing numbers (Q986698)
From MaRDI portal
| This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: On the sharpness of some results relating cuts and crossing numbers |
scientific article; zbMATH DE number 5769511
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On the sharpness of some results relating cuts and crossing numbers |
scientific article; zbMATH DE number 5769511 |
Statements
On the sharpness of some results relating cuts and crossing numbers (English)
0 references
12 August 2010
0 references
Summary: 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.
0 references
connectivity condition
0 references
0.87944037
0 references
0.87189054
0 references
0.8661205
0 references
0.8657347
0 references
0 references
0.86170053
0 references
0.8574182
0 references
0.8571359
0 references