Crossing numbers of complete bipartite graphs and complete graphs

  • Authors

    • Sanjith Hebbar
    • Tabitha Agnes Mangam
    https://doi.org/10.14419/ijet.v7i4.21528

  • The crossing number of a graph is the smallest number of two edge crossings over all planar representations of the graph. In this paper, we investigate the crossing numbers of complete bipartite and complete graphs. Further, we identify optimal drawings and present results on crossing numbers of these classes of graphs. In addition, Zarankiewicz's conjecture on complete bipartite graphs and Guy's conjecture on complete graphs are verified to be true.

  • References

    1. [1] Leighton,F. T. Complexity Issues in VLSI. MIT Press, 1983.

      [2] Harary,F. Graph Theory, Narosa Publishing House, 2001.

      [3] Guy, R. K. "The Decline and fall of Zarankiewicz's Theorem." In Proof Techniques in Graph Theory, Proceedings of the Second Ann Arbor Graph Theory Conference, Ann Arbor, Michigan, 1968. New York: Academic Press, pp. 63-69, 1969.

      [4] Kleitman,D.J. The crossing number of K5, n, J.Combinat. Theory 9 (1970) 315-323. https://doi.org/10.1016/S0021-9800(70)80087-4.

      [5] Woodall, D. R. "Cyclic-Order Graphs and Zarankiewicz's Crossing-Number Conjecture." J. Graph Th. 17, 657-671, and 1993.

      [6] Guy, R. K. "Crossing Numbers of Graphs." In Graph Theory and Applications: Proceedings of the Conference at Western Michigan University, Kalamazoo, Mich., May 10-13, 1972 (E d. Y. Alavi, D. R. Lick, and A. T. White). New York: Springer-Verlag, pp. 111-124, 1972. https://doi.org/10.1007/BFb0067363.

      [7] Pan, S. and Richter, R. B. "The Crossing Number of K11 is 100." J. Graph Th. 56, 128-134, and 2007.

  • Downloads

  • How to Cite

    Hebbar, S., & Mangam, T. A. (2018). Crossing numbers of complete bipartite graphs and complete graphs. International Journal of Engineering & Technology, 7(4), 2996-3000. https://doi.org/10.14419/ijet.v7i4.21528