×

zbMATH — the first resource for mathematics

On the crossing numbers of Cartesian products of stars and paths or cycles. (English) Zbl 0755.05067
Summary: The main results of this paper show that the crossing number of the Cartesian product \(S_ 4\times P_ n\) is \(2(n-1)\) for \(n\geq 1\) and that the crossing number of the Cartesian product \(S_ 4\times C_ n\) is \(2n\) for \(n\geq 6\). We also get the crossing numbers of \(S_ 4\times C_ 3\), \(S_ 4\times C_ 4\) and \(S_ 4\times C_ 5\).

MSC:
05C38 Paths and cycles
PDF BibTeX XML Cite
Full Text: EuDML
References:
[1] ERDÖS P., GUY R. K.: Crossing number problems. Amer. Math. Monthly, 80, 1973, 52-58. · Zbl 0264.05109
[2] HARARY F.: Graph Theory. Addison-Wesley, Reading Mass. 1969. · Zbl 0196.27202
[3] JENDROĽ S., ŠČERBOVÁ M.: On the crossing numbers of Sm x Pn, and Sm x Cn. Časopis pro pěstování matematiky, 107, 1982, 225-230.
[4] KLEITMAN D. J.: The crossing number of K5. n. J. Combinatorial Theory B, 9, 1970, 315-323. · Zbl 0205.54401
[5] KOMAN M.: On the crossing numbers of graphs. Acta Univ. Carolinae Math. Phys., 10, 1969, 9-46. · Zbl 0256.05103
[6] RINGEISEN R. D., BEINEKE L. W.: The crossing number of C3 x Cn. J. Combinatorial Theory B, 24, 1978, 134- 136. · Zbl 0383.05015
[7] RINGEISEN R. D., BEINEKE L. W.: On the crossing numbers of product of cycles and graphs of order four. J. Graph Theory, 4, 1980, 145-155. · Zbl 0403.05037
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.