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

Vasanthi Beulah P.

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.


Keywords


drawing of a graph, crossing number, union and join of graphs, path, cycle.

Full Text:

PDF

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.


Refbacks

  • There are currently no refbacks.


Copyright (c) 2016 Journal of Progressive Research in Mathematics

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

Copyright © 2016 Journal of Progressive Research in Mathematics. All rights reserved.

ISSN: 2395-0218.

For any help/support contact us at editorial@scitecresearch.com, jprmeditor@scitecresearch.com.