{"entities":{"Q944744":{"pageid":946592,"ns":120,"title":"Item:Q944744","lastrevid":50452106,"modified":"2026-01-14T02:22:28Z","type":"item","id":"Q944744","labels":{"en":{"language":"en","value":"On the crossing numbers of \\(K_m\\square C_n\\) and \\(K_{m,l}\\square P_n\\)"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5324160"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q944744$F36F600B-161A-4F06-B427-813285BC454A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6d879fc0c930e78f293ffcfd5efc8558a7799bce","datavalue":{"value":{"text":"On the crossing numbers of \\(K_m\\square C_n\\) and \\(K_{m,l}\\square P_n\\)","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q944744$3D120B60-9F6A-470B-A611-CF8FD0DE73C1","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"62f6b48a4b8c5ca0a2127696bbd8b4a30bb7f651","datavalue":{"value":"1161.05030","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q944744$2BA4242A-E713-405F-AF76-D30A59217738","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c553b175b3ac24d798467f2cc8906dd58ce57911","datavalue":{"value":{"entity-type":"item","numeric-id":944741,"id":"Q944741"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q944744$DE429B8E-A834-4F9F-A1DA-38087EA0449E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"17f1ae69805e2c73bc569d3d1198a05ccb67e507","datavalue":{"value":{"entity-type":"item","numeric-id":944742,"id":"Q944742"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q944744$8495AA13-E079-499B-8B25-993861DCB700","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"26182120854703deb6ac89dfb33caad39aee4c88","datavalue":{"value":{"entity-type":"item","numeric-id":479057,"id":"Q479057"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q944744$76720218-CAC2-4FB1-8862-6DDB8F5CD41E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c728f49fe418c870e8ab0881b1717ae8ee92f211","datavalue":{"value":{"entity-type":"item","numeric-id":944743,"id":"Q944743"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q944744$AC4231C5-47D6-4C5D-A10A-D26B004E570E","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q944744$A1BF2877-ABEE-476A-B445-BE2801A7C908","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"131b596fa601c3661806f2437747b7af2f563219","datavalue":{"value":{"time":"+2008-09-10T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q944744$BE77AB81-4F51-443F-A6EC-FBA687B502BB","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6dcf66643728c7eba9beda24d59da372c5e0369c","datavalue":{"value":"Let \\(G_1\\square G_2\\) be the Cartesian product of two graphs \\(G_1\\) and \\(G_2\\). \\textit{R. D. Ringeisen} and \\textit{L. W. Beineke} [J. Comb. Theory, Ser. B 24, 134--136 (1978; Zbl 0383.05015)] have proved that \\(cr(C_3\\square C_n)=n\\) and \\(cr(K_4\\square C_n)=3n\\). \\textit{D. Bokal} [J. Comb. Theory, Ser. B 97, 381--384 (2007; Zbl 1113.05027)] has proved that \\(cr(K_{1,l}\\square P_n)=(n-1)\\lfloor \\frac l2\\rfloor\\lfloor\\frac{l-1}2\\rfloor\\). In this paper the authors study the crossing numbers of \\(K_m\\square C_n\\) and \\(K_{m,l}\\square P_n\\), and show that  {\\parindent=7mm \\begin{itemize}\\item[(i)]\\(cr(K_m\\square C_n)\\geq n\\cdot cr(K_{m+2})\\) for \\(n\\geq3\\) and \\(m\\geq5\\);  \\item[(ii)]\\(cr(K_m\\square C_n)\\leq\\frac n4\\lfloor\\frac{m+2}2\\rfloor\\lfloor\\frac {m+1}2\\rfloor\\lfloor\\frac m2\\rfloor\\lfloor\\frac{m-1}2\\rfloor\\) for \\(m=5,6,7\\) and for \\(m\\geq8\\) with even \\(n\\geq4\\), and equality holds for \\(m=5,6,7\\) and for \\(m=8,9,10\\) with even \\(n\\geq4\\) and  \\item[(iii)]\\(cr(K_{m,l}\\square P_n)\\leq(n-1)(\\lfloor\\frac{m+2}2\\rfloor\\lfloor\\frac{m+1}2\\rfloor\\lfloor\\frac{l+2}2\\rfloor\\lfloor\\frac{l+1}2\\rfloor-ml)+2(\\lfloor\\frac{m+1}2\\rfloor\\lfloor\\frac m2\\rfloor\\lfloor\\frac{l+1}2\\rfloor\\lfloor\\frac l2\\rfloor-\\lfloor\\frac m2\\rfloor\\lfloor\\frac l2\\rfloor)\\) for \\(\\min(m,l)\\geq2\\), and equality holds for \\(\\min(m,l)=2\\).  \\end{itemize}}","type":"string"},"datatype":"string"},"type":"statement","id":"Q944744$9FBE1D37-5A15-405D-99E9-DC69FF118556","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q944744$8A484438-D013-466D-91D8-200D720D6D9E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f4bae4cf622e1938dd06cf12c6fd377b6d615b44","datavalue":{"value":"5324160","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q944744$4381BCD1-5CC7-4EBA-A4A4-622C41228621","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0b3cd79844fe61c30e9704e9d6964230fcd1067f","datavalue":{"value":"Crossing number","type":"string"},"datatype":"string"},"type":"statement","id":"Q944744$24E8DF07-5191-4BE8-AD15-76E454C370EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c7642d8b032ac6ec79fcbf380f24fdc21e9f421e","datavalue":{"value":"Cartesian product","type":"string"},"datatype":"string"},"type":"statement","id":"Q944744$E704CD09-AABA-4FE6-8CA2-DEE23D19E95E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5a38ff7447aeeeb80eb7c25caf51312b53bbe73b","datavalue":{"value":"Complete graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q944744$375BD76D-983F-4021-B0B9-B0916ECCD30F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b9dbe276b98a95ddeb9ffd6317b913f22947fc60","datavalue":{"value":"Complete bipartite graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q944744$0ED09461-C995-4C8C-A674-6429FBEC1835","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"02baa8c7a177bdddffdd29a44a9d552f63adf459","datavalue":{"value":{"entity-type":"item","numeric-id":582576,"id":"Q582576"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q944744$6F7BE592-BD05-4F35-883B-6CF831943F04","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q944744$0A68520B-34E6-42FE-B337-2BC0766F46FE","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9b00d5372e1b2b7657dec84b16596d7e81e92a59","datavalue":{"value":"https://doi.org/10.1016/j.dam.2007.09.007","type":"string"},"datatype":"url"},"type":"statement","id":"Q944744$5D46F322-9A6D-475E-9B94-B238B1AE88E8","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"9acb2dfc24327256e0f37f3781a0dcdf0a907978","datavalue":{"value":"W12384564","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q944744$71793537-B2E3-42B9-8124-B08E6CD349BC","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"9decc168703a2b3126ee99ef3ad2e44f1cf055b1","datavalue":{"value":{"entity-type":"item","numeric-id":4390601,"id":"Q4390601"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q944744$8E76C620-3888-4E2A-8BF2-7C5172FF44F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0ce325a59280dc05cd517cc6b25beb18f6aa25a7","datavalue":{"value":{"entity-type":"item","numeric-id":3712347,"id":"Q3712347"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q944744$78E4F79D-14BA-4059-AEF8-02CEB5E0A17F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c752c6c7a682bd4f259b65fb86498a176551755","datavalue":{"value":{"entity-type":"item","numeric-id":4187846,"id":"Q4187846"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q944744$CBF809D5-6EED-49C5-A40D-B570DEB5AE5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8096df8791cf776a33603b62276b064106ad05bc","datavalue":{"value":{"entity-type":"item","numeric-id":3856672,"id":"Q3856672"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q944744$114D7B9A-2451-4607-9C09-FDEE6A9505B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"58b868c7837e17d1bb5bafa5c2d0c1625cdd7c66","datavalue":{"value":{"entity-type":"item","numeric-id":875940,"id":"Q875940"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q944744$7B51AF3E-79FD-47F6-883D-02CFBE5E5FC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e8e3f0686a125c925bbca5b9b6a54e0de625b3c3","datavalue":{"value":{"entity-type":"item","numeric-id":4748171,"id":"Q4748171"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q944744$35E32CD9-34A4-4E52-A316-5D53C37FDD47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"981d12cf3fffb4d26713164dc5037b484dbc6735","datavalue":{"value":{"entity-type":"item","numeric-id":5605750,"id":"Q5605750"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q944744$1F222A97-AC96-4D6A-901A-30C70F0D25DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c50e8e2a726cf79900009e3a4cbe41181e7baf3a","datavalue":{"value":{"entity-type":"item","numeric-id":4018745,"id":"Q4018745"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q944744$F34F0546-6AEB-46F8-86F3-ED65A3A2D572","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ef45643405e5facc8e5ba856b81b64c888c6028d","datavalue":{"value":{"entity-type":"item","numeric-id":4309988,"id":"Q4309988"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q944744$46D642D8-C8DB-4ACA-9AFF-1E375CE7235A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ac0ef94a26f9d6d93c9a6923cd0b1bf0d37e9459","datavalue":{"value":{"entity-type":"item","numeric-id":4846680,"id":"Q4846680"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q944744$2A975525-17D6-4048-AE1C-1CA0CA937C0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f67ce385b8ffd82fd2b908dfef51fc0d8dfe14ea","datavalue":{"value":{"entity-type":"item","numeric-id":4882472,"id":"Q4882472"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q944744$0F6A383C-D6B5-4AF5-9C49-BAB6324DBEFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c7f048d6af3971ef389782253ea6ee30ff708ca6","datavalue":{"value":{"entity-type":"item","numeric-id":4518402,"id":"Q4518402"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q944744$0A1B77E5-D3A1-4F6B-A923-CF7E782D9DAE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ec2e8c01b4aab69d4985a8fbfbac5703f824491","datavalue":{"value":{"entity-type":"item","numeric-id":5936042,"id":"Q5936042"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q944744$944907C7-63F0-4D65-AF43-9E6CD70B63C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"72dc49f28ce7907def0bf29c6fe50dd8957b92a9","datavalue":{"value":{"entity-type":"item","numeric-id":5943048,"id":"Q5943048"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q944744$D287D818-42C2-44F1-A871-897C0AFCB1FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"960eb712508409c23a3a5e959f088a75c457a36f","datavalue":{"value":{"entity-type":"item","numeric-id":1248631,"id":"Q1248631"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q944744$48B71676-9A71-4B73-B425-592F10B2F7B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e8b782bb0f8e5852bc0c9dabf0fe4fd5648d456b","datavalue":{"value":{"entity-type":"item","numeric-id":4285587,"id":"Q4285587"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q944744$5FAA4BFE-1CC8-45C0-9008-D844646CAFD6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3ef60d374d08c8f2c52c65fece0997012e730e56","datavalue":{"value":{"entity-type":"item","numeric-id":5827570,"id":"Q5827570"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q944744$CF436544-3543-4FC1-B5E3-84E47322AF26","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4473d0d183f2fc1f5bb04e2daea5c8a601501e36","datavalue":{"value":{"entity-type":"item","numeric-id":998409,"id":"Q998409"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q944744$7F9DA0A4-BD0A-4AF9-8EC3-AF5073719C0C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6d0531665153b36d556ac078145a93fd642f259c","datavalue":{"value":"10.1016/J.DAM.2007.09.007","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q944744$2D3F834C-2901-4BCC-AFF0-DA6DB801AC5D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"280aaf7676f9f4a088194f450592651d3911d9ec","datavalue":{"value":{"entity-type":"item","numeric-id":995761,"id":"Q995761"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ca618f1f5e3446a00f5b3cb451fd36277aab15c6","datavalue":{"value":{"amount":"+0.932581663131714","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q944744$836E27E7-7A61-485B-978E-ED76764EBA66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"05ade59a67558ab8907d87f5024349c9d152c010","datavalue":{"value":{"entity-type":"item","numeric-id":2881277,"id":"Q2881277"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7023217d7ed017d0ee9254e6f30569f9f946cf9d","datavalue":{"value":{"amount":"+0.9022747874259948","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q944744$F35D9E46-882A-4844-ABC8-0657EF27B1E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"634fc04e25d90a7d023cea1da2492de905159d7b","datavalue":{"value":{"entity-type":"item","numeric-id":5017911,"id":"Q5017911"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"308e54abcc078384a42a7380f62de0e705a9ee5f","datavalue":{"value":{"amount":"+0.8954618573188782","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q944744$1CB5AAAD-7D6F-4C7E-95E4-A49A0C98699C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1e3d149350ce59160c57074fec3fc8c24c3df6c6","datavalue":{"value":{"entity-type":"item","numeric-id":3131839,"id":"Q3131839"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"45a472880fe5add14a757d8734fce0797d87e242","datavalue":{"value":{"amount":"+0.8868193030357361","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q944744$C000C726-86DB-4DDD-BCCF-F5CA05CE41AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2f7a8fa1e518f04e8686abcd1d5edff86bab0129","datavalue":{"value":{"entity-type":"item","numeric-id":432699,"id":"Q432699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4737415042ebce804ae3d64240a2b85914cc484b","datavalue":{"value":{"amount":"+0.8832871317863464","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q944744$C30D3191-45D7-4AD9-83DA-68EDEABBBB89","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:944744","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:944744"}}}}}