Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
The splitting number of the 4-cube
| |
|
The splitting number of the 4-cube
Luerbio Faria1, 3 , Celina Miraglia Herrera de Figueiredo2, 3 and Candido Ferreira Xavier de MendonÇa Neto4 
| (1) |
Faculdade de FormaÇÃo de Professores, UERJ, Brazil |
| (2) |
Instituto de Matemática, UFRJ, Brazil |
| (3) |
COPPE Sistemas e ComputaÇÃo, UFRJ, Brazil |
| (4) |
Instituto de ComputaÇÃo, UNICAMP, Brazil |
Abstract
The splitting number of a graph G is the smallest integer k ≥ 0 such that a planar graph can be obtained from G by k splitting operations. Such operation replaces v by two nonadjacent vertices v
1 and v
2, and attaches the neighbors of v either to v
1 or to v
2. The n-cube has a distinguished plaice in Computer Science. Dean and Richter devoted an article to proving that the minimum number
of crossings in an optimum drawing of the 4-cube is 8, but no results about splitting number of other nonplanar n-cubes are known. In this note we give a proof that the splitting number of the 4-cube is 4. In addition, we give the lower
bound 2
n−2 for the splitting number of the n-cube. It is known that the splitting number of the n-cube is O(2n), thus our result implies that the splitting number of the n-cube is λ(2n).
Work partially supported by CNPq, CAPES, FAPERJ and FAPESP, Brazilian research agencies.
Fulltext Preview (Small, Large)
 References secured to subscribers.
|
|
|
|
|
|