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

Vasanthi Beulah P.

Vasanthi Beulah P. Assistant Professor Department of Mathematics, Queen Mary's College, University of Madras, Chennai, India

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

Downloads

Download data is not yet available.

Author Biography

Vasanthi Beulah P., Assistant Professor Department of Mathematics, Queen Mary's College, University of Madras, Chennai, India

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.