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.
My Menu
Saved Items

The splitting number of the 4-cube

Luerbio Faria1, 3 Contact Information, Celina Miraglia Herrera de Figueiredo2, 3 Contact Information and Candido Ferreira Xavier de MendonÇa NetoContact Information

(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.

Contact Information Luerbio Faria
Email: luerbio@cos.ufrj.br

Contact Information Celina Miraglia Herrera de Figueiredo
Email: celina@cos.ufrj.br

Contact Information Candido Ferreira Xavier de MendonÇa Neto
Email: xavier@dcc.unicamp.br
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.109 • Server: mpweb06
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)