An upper bound for the crossing number of augmented cubes

References

• Bhatt , S. N. and Leighton , F. T. 1984 . A framework for solving VLSI graph layout problems . J. Comput. System Sci. , 28 : 300 – 343 . (doi:10.1016/0022-0000(84)90071-0)
   Web of Science ®Google Scholar
• Bhuyan , L. and Agrawal , D. P. 1984 . Generalized hypercubes and hyperbus structure for a computer network . IEEE Trans. Comput. , 33 : 323 – 333 . (doi:10.1109/TC.1984.1676437)
   Web of Science ®Google Scholar
• Chan , H. C. , Chang , J. M. , Wang , Y. L. and Horng , S. J. 2009 . Geodesic-pancyclicity and fault-tolerant panconnectivity of augmented cubes . Appl. Math. Comput. , 207 : 333 – 339 . (doi:10.1016/j.amc.2008.10.061)
   Web of Science ®Google Scholar
• Chang , N. W. and Hsieh , S. Y. 2012 . Conditional diagnosability of augmented cubes under the PMC model . IEEE Trans. Dependable and Secure Comput. , 9 : 46 – 60 . (doi:10.1109/TDSC.2010.59)
   Web of Science ®Google Scholar
• Choudum , S. A. and Sunitha , V. 2002 . Augmented cubes . Networks , 40 : 71 – 84 . (doi:10.1002/net.10033)
   Web of Science ®Google Scholar
• Dean , A. M. and Richter , R. B. 1995 . The crossing number of . J. Graph Theory , 19 : 125 – 129 . (doi:10.1002/jgt.3190190113)
   Web of Science ®Google Scholar
• Eggleton , R. B. and Guy , R. K. 1970 . The crossing number of the n-cube . Not. Amer. Math. Soc. , 17 : 757 – 757 .
   Web of Science ®Google Scholar
• Erdős , P. and Guy , R. K. 1973 . Crossing number problems . Amer. Math. Monthly , 80 : 52 – 58 . (doi:10.2307/2319261)
   Google Scholar
• Faria , L. and de Figueiredo , C. M.H. 2000 . On Eggleton and Guy's conjectured upper bound for the crossing number of the n-cube . Math. Slovaca , 50 : 271 – 287 .
   Google Scholar
• Faria , L. , de Figueiredo , C. M.H. , Sykora , O. and Vrt'o , I. 2008 . An improved upper bound on the crossing number of the hypercube . J. Graph Theory , 59 : 145 – 159 . (doi:10.1002/jgt.20330)
   Web of Science ®Google Scholar
• Garey , M. R. and Johnson , D. S. 1983 . Crossing number is NP-complete . SIAM J. Alg. Disc. Math. , 4 : 312 – 316 . (doi:10.1137/0604033)
   Google Scholar
• Guy , R. K. 1960 . A combinatorial problem . Nabla (Bull. Malayan Math. Soc.) , 7 : 68 – 72 .
   Google Scholar
• Hong , W. S. and Hsieh , S. Y. 2012 . Strong diagnosability and conditional diagnosability of augmented cubes under the comparison diagnosis model . IEEE Trans. Reliab. , 61 : 140 – 148 . (doi:10.1109/TR.2011.2170105)
   Web of Science ®Google Scholar
• Hsieh , S. Y. and Cian , Y. R. 2010 . Conditional edge-fault Hamiltonicity of augmented cubes . Inform. Sci. , 180 : 2596 – 2617 . (doi:10.1016/j.ins.2010.03.005)
   Web of Science ®Google Scholar
• Hsieh , S. Y. and Shiu , J. Y. 2007 . Cycle embedding of augmented cubes . Appl. Math. Comput. , 191 : 314 – 319 . (doi:10.1016/j.amc.2007.02.089)
   Web of Science ®Google Scholar
• Hsu , H. C. , Chiang , L. C. , Tan , J. J.M. and Hsu , L. H. 2005 . Fault Hamiltonicity of augmented cubes . Parallel Comput. , 31 : 130 – 145 . (doi:10.1016/j.parco.2004.10.002)
   Google Scholar
• Hsu , H. C. , Lai , P. L. and Tsai , C. H. 2007 . Geodesic pancyclicity and balanced pancyclicity of augmented cubes . Inform. Process. Lett. , 101 : 227 – 232 . (doi:10.1016/j.ipl.2006.10.013)
   Web of Science ®Google Scholar
• Lee , C. M. , Teng , Y. H. , Jimmy , J. M. , Tanc and Hsu , L. H. 2009 . Embedding Hamiltonian paths in augmented cubes with a required vertex in a fixed position . Comput. Math. Appl. , 58 : 1762 – 1768 . (doi:10.1016/j.camwa.2009.07.079)
   Web of Science ®Google Scholar
• Leighton , F. T. 1983 . Complexity Issues in VLSI , Cambridge , MA : MIT Press . Foundations of Computer Series
   Google Scholar
• Leighton , F. T. 1984 . New lower bound techniques for VLSI . Math. Systems Theory , 17 : 47 – 70 . (doi:10.1007/BF01744433)
   Google Scholar
• Leighton , F. T. 1992 . Introduction to Parallel Algorithms and Architecture: Arrays, Trees, Hypercubes , San Mateo , CA : Morgan Kaufmann .
   Google Scholar
• Lin , X. H. , Yang , Y. S. , Zheng , W. P. , Shi , L. and Lu , W. M. 2009 . The crossing numbers of generalized Petersen graphs with small order . Discrete Appl. Math. , 157 : 1016 – 1023 . (doi:10.1016/j.dam.2008.01.012)
   Web of Science ®Google Scholar
• Ma , M. , Liu , G. and Xu , J. M. 2007 . Panconnectivity and edge-fault-tolerant pancyclicity of augmented cubes . Parallel Comput. , 33 : 35 – 42 . (doi:10.1016/j.parco.2006.11.008)
   Google Scholar
• Madej , T. 1991 . Bounds for the crossing number of the n-cube . J. Graph Theory , 15 : 81 – 97 . (doi:10.1002/jgt.3190150109)
   Web of Science ®Google Scholar
• Pan , S. and Richter , R. B. 2007 . The crossing number of K11 is 100 . J. Graph Theory , 56 : 128 – 134 . (doi:10.1002/jgt.20249)
   Web of Science ®Google Scholar
• Richter , R. B. and Thomassen , C. 1995 . Intersections of curve systems and the crossing number of . Discrete Comput. Geom. , 13 : 149 – 159 . (doi:10.1007/BF02574034)
   Web of Science ®Google Scholar
• Salazar , G. 2005 . On the crossing numbers of loop networks and generalized Petersen graphs . Discrete Math. , 302 : 243 – 253 . (doi:10.1016/j.disc.2004.07.036)
   Web of Science ®Google Scholar
• Sykora , O. and Vrt'o , I. 1993 . On crossing numbers of hypercubes and cube connected cycles . BIT , 33 : 232 – 237 . (doi:10.1007/BF01989746)
   Google Scholar
• Turán , P. 1977 . A note of welcome . J. Graph Theory , 1 : 7 – 9 . (doi:10.1002/jgt.3190010105)
   Google Scholar
• Tutte , W. T. 1970 . Toward a theory of crossing numbers . J. Combin. Theory , 8 : 45 – 53 . (doi:10.1016/S0021-9800(70)80007-2)
   Google Scholar
• Wang , W. W. , Ma , M. J. and Xu , J. M. 2007 . Fault-tolerant pancyclicity of augmented cubes . Inform. Process. Lett. , 103 : 52 – 56 . (doi:10.1016/j.ipl.2007.02.012)
   Web of Science ®Google Scholar
• Xu , M. and Xu , J. M. 2007 . The forwarding indices of augmented cubes . Inform. Process. Lett. , 101 : 185 – 189 . (doi:10.1016/j.ipl.2006.09.013)
   Web of Science ®Google Scholar
• Yang , Y. S. , Wang , G. Q. , Wang , H. L. and Zhou , Y. “ The Erdős and Guy's conjectured equality on the crossing number of hypercubes ” . preprint (2012). Available at arXiv:1201.4700v1
   Google Scholar