On the Crossing Number of Join of some Graphs of order six with nK1, Path and Cycle

  • Vasanthi Beulah P. Queen Mary's College, University of Madras, CHEENAI
Keywords: drawing of a graph, crossing number, union and join of graphs, path, cycle.

Abstract

It has been long conjectured by Zarankiewicz, the crossing number of the
complete bipartite graph Km;n. This conjecture has been veried by Kleitman  for min {m, n}<= 6. Using this result, we give the exact value of crossing number of the join of a certain graph G on six vertices with nK1, Pn and Cn, an empty graph, a path and a cycle respectively on n vertices.

Author Biography

Vasanthi Beulah P., Queen Mary's College, University of Madras, CHEENAI

Assistant Professor

Department of Mathematics

Queen Mary's College, 

CHEENAI - 600004

References

S.N. Bhatt and F.T. Leighton, A framework for solving VLSI graph

layout problems, J. Comput. System Sci. 28, pp. 300343, 1984.

F. T. Leighton, Complexity Issues in VLSI, MIT Press, Cambridge,

Mass., 1983.

F. T. Leighton, New lower bound techniques for VLSI, Math. Systems

Theory vol 17, pp. 4770, 1984.

L. A. Székely, A Successful Concept for Measuring Nonplanarity of

Graphs: the Crossing Number, Discrete Math. vol 276, pp. 331352,

M.R. Garey, D.S. Johnson, Crossing Number is NPComplete, SIAM

J. Alg. Disc. Meth, vol 4, pp. 312316, 1983.

He Pei Ling, Qian Chun, Ouyang Zhang Dong, Hung Yuan Qiu, "The

Crossing Number of Cartesian Products of stars and 5-Vertex Graphs",

Journal of Mathematical Research Exposition, 29 (2009) 335-342.

M.Klesc, "The join of graphs and crossing numbers", Electronic notes

in Discrete Math., 28(2007) 349-355.

M. Klesc, The crossing number of the join of the special graph on

six vertices with path and cycle, Discrete Mathematics, vol. 310, pp.

1481, 2010

V.R. Kulli, M.H..Muddebihal, "Characterization of join graphs with

crossing number zero". Far East J. Appl. Math. 5 (2001) 87-97.

D. J.Kleitman, "The crossing number of K5;n, " J. Combin. Theory B

(1971), 315323.

Published
2016-12-01
How to Cite
P., V. (2016). On the Crossing Number of Join of some Graphs of order six with nK1, Path and Cycle. Journal of Progressive Research in Mathematics, 10(1), 1440-1445. Retrieved from http://scitecresearch.com/journals/index.php/jprm/article/view/938
Section
Articles