PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2011 | 31 | 2 | 321-331
Tytuł artykułu

The crossing numbers of join products of paths with graphs of order four

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
Kulli and Muddebihal [V.R. Kulli, M.H. Muddebihal, Characterization of join graphs with crossing number zero, Far East J. Appl. Math. 5 (2001) 87-97] gave the characterization of all pairs of graphs which join product is planar graph. The crossing number cr(G) of a graph G is the minimal number of crossings over all drawings of G in the plane. There are only few results concerning crossing numbers of graphs obtained as join product of two graphs. In the paper, the exact values of crossing numbers for join of paths with all graphs of order four, as well as for join of all graphs of order four with n isolated vertices are given.
Słowa kluczowe
Wydawca
Rocznik
Tom
31
Numer
2
Strony
321-331
Opis fizyczny
Daty
wydano
2011
otrzymano
2009-11-30
poprawiono
2010-06-22
zaakceptowano
2010-06-28
Twórcy
  • Department of Mathematics, Faculty of Electrical Engineering and Informatics, Technical University, 042 00 Košice, Slovak Republic
  • Department of Mathematics, Faculty of Electrical Engineering and Informatics, Technical University, 042 00 Košice, Slovak Republic
Bibliografia
  • [1] K. Asano, The crossing number of $K_{1,3,n}$ and $K_{2,3,n}$, J. Graph Theory 10 (1986) 1-8, doi: 10.1002/jgt.3190100102.
  • [2] L.W. Beineke and R.D. Ringeisen, On the crossing numbers of products of cycles and graphs of order four, J. Graph Theory 4 (1980) 145-155, doi: 10.1002/jgt.3190040203.
  • [3] D. Bokal, On the crossing numbers of Cartesian products with paths, J. Combin. Theory (B) 97 (2007) 381-384, doi: 10.1016/j.jctb.2006.06.003.
  • [4] M.R. Garey and D.S. Johnson, Crossing number is NP-complete, SIAM J. Algebraic. Discrete Methods 4 (1983) 312-316, doi: 10.1137/0604033.
  • [5] L.Y. Glebsky and G. Salazar, The crossing number of Cₘ ×Cₙ is as conjectured for n ≥; m(m+1), J. Graph Treory 47 (2004) 53-72, doi: 10.1002/jgt.20016.
  • [6] F. Harary, P.C. Kainen and A.J. Schwenk, Toroidal graphs with arbitrarily high crossing numbers, Nanta Math. 6 (1973) 58-67.
  • [7] S. Jendrol' and M. Scerbová, On the crossing numbers of Sₘ ×Pₙ and Sₘ ×Cₙ, Casopis pro pestování matematiky 107 (1982) 225-230.
  • [8] M. Klešč, The crossing numbers of Cartesian products of paths with 5-vertex graphs, Discrete Math. 233 (2001) 353-359, doi: 10.1016/S0012-365X(00)00251-X.
  • [9] M. Klešč, The join of graphs and crossing numbers, Electronic Notes in Discrete Math. 28 (2007) 349-355, doi: 10.1016/j.endm.2007.01.049.
  • [10] D.J. Kleitman, The crossing number of $K_{5,n}$, J. Combin. Theory (B) 9 (1971) 315-323.
  • [11] V.R. Kulli and M.H. Muddebihal, Characterization of join graphs with crossing number zero, Far East J. Appl. Math. 5 (2001) 87-97.
  • [12] K. Zarankiewicz, On a problem of P. Turán concerning graphs, Fund. Math. 41 (1954) 137-145.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1548
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.