{"entities":{"Q1109047":{"pageid":1119796,"ns":120,"title":"Item:Q1109047","lastrevid":66687537,"modified":"2026-04-12T11:59:05Z","type":"item","id":"Q1109047","labels":{"en":{"language":"en","value":"Scattering number and extremal non-Hamiltonian graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4068917"}},"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":"Q1109047$E1551B6D-9158-4B82-827E-CB984F4174A1","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f1427852ed861e683f2dfb65db0d1f3a8ef45b91","datavalue":{"value":{"text":"Scattering number and extremal non-Hamiltonian graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1109047$EEC3F69D-65FF-437B-B0F6-4FA47A1E91AE","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0bc111ddb2a6ac87556a443a7f52284c6955dfe7","datavalue":{"value":"0655.05044","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109047$82A35FF6-9CCA-4976-9E11-3481F77C7FA5","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ad67527bccaa16803dccf57d14b50a72d10103e3","datavalue":{"value":"10.1016/0012-365X(88)90069-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109047$3D4991BF-A2C4-4514-AE67-DFE2119403C5","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1dd4499b3b6a5777471075da03b2fe8244ffc7d9","datavalue":{"value":{"entity-type":"item","numeric-id":750460,"id":"Q750460"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109047$DD2669EA-4277-4A2E-8F08-21715D4652EF","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109047$8C2CF9AF-B132-428E-868D-75FDC2BDAD82","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1109047$4C82582E-7D14-4B8A-BDCE-11337AD09EA1","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"43a402abfa74da74c55eb5bd3cf6b80d531ffc9b","datavalue":{"value":"The scattering number, s(G), of a graph G is defined by \\(s(G)=\\max \\{k(G- X)-| X|;\\quad X\\subseteq V(G),\\quad k(G-X)\\neq 1\\},\\) where k(H) denotes the number of components of the graph H. Let \\(Q_ 0\\), \\(Q_ 1\\) and \\(Q_ 2\\) stand for the words traceable, Hamiltonian and Hamiltonian- connected (every pair of vertices is connected by a Hamiltonian path), respectively.    In the paper the following conjecture is stated: Let h and i be integers with \\(h\\geq 0\\) and \\(0\\leq i\\leq 2\\). There exists an integer N(h,i) such that if G is a graph with order \\(n\\geq N(h,i)\\), size \\(q\\geq \\left( \\begin{matrix} n-2h- 3\\\\ 2\\end{matrix} \\right)+(2h+3)(h+i+1)\\) and scattering number s(G)\\(\\leq 1- h-i\\) then either G is in \\(Q_ i\\) or \\(G\\simeq K_{h+i}+A_{n-3h-i- 3,2h+3}\\) where, for \\(p\\geq r\\), \\(A_{p,r}\\) denotes the graph of order \\(p+r\\) obtained by identifying an end vertex of each edge of \\(rK_ 2\\) with a distinct vertex of \\(K_ p.\\)    The author proves the conjecture for \\(h=0\\) and \\(i=0,1,2\\) \\((N(0,i)=19+i)\\) and \\(h=1\\) and \\(i=0\\) \\((N(1,0)=31)\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109047$6A8F177E-D569-4603-A0EE-9E72E41F8804","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"eef1b49f4a66afb755b22d7419db9d61ba07415f","datavalue":{"value":"05C45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109047$31CD09F0-3966-4892-B250-8BFA08600947","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109047$D4D4DEF9-312B-4D98-AB54-145894960F79","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"572ecfc68b49c41f8600b5550b4497a0c9e08486","datavalue":{"value":"4068917","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109047$233C024F-AF28-4762-8F7F-592E9CF4BADD","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e9a04a453e91c79c7e831d838f6c5e3a9e0859a2","datavalue":{"value":"scattering number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109047$1A5EA181-448F-4BD6-AD75-8DA13E77279B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1b192458bf3e522f8d2259357613260c470fc9a0","datavalue":{"value":"traceable","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109047$663DDD05-73CD-4F7A-8039-5220175CD42B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c822c54638e4070b56aee42666fe01efcdddece8","datavalue":{"value":"Hamiltonian","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109047$AD9702F1-751E-4283-854B-F142BFC21E12","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"46e40a3dbd7f40523825d72d301e4da63374b7cf","datavalue":{"value":"Hamiltonian-connected","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109047$53893F52-67EC-4ADC-B604-38A2411EE531","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"ef22b67971c907f35c542e2435922e6c49358d32","datavalue":{"value":{"entity-type":"item","numeric-id":215558,"id":"Q215558"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109047$2CDBD55F-52DF-49D4-9368-F75D3AFD7891","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":"Q1109047$5C48D27B-8ACD-4DCB-BD56-348686CC2F29","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"fa6b88d7c0c035ddcdc73a99f8a04d3f8ce9fbcc","datavalue":{"value":{"entity-type":"item","numeric-id":4187840,"id":"Q4187840"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109047$94EA6327-911E-4086-B7D1-E60E6889B47D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bdc91c6e93789ee17e248c1697a54c42f85472a6","datavalue":{"value":{"entity-type":"item","numeric-id":5648389,"id":"Q5648389"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109047$1228490B-1348-44F6-8DE0-F1A6EF525DB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dcd492719f080c59c4dd23730fc178cf5a672a45","datavalue":{"value":{"entity-type":"item","numeric-id":1227760,"id":"Q1227760"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109047$4AA75B8E-22C7-4EEC-A3A4-C98724303392","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"11fbb5ee59c3c5fba8b68dc26e64c473270f6227","datavalue":{"value":{"entity-type":"item","numeric-id":2545100,"id":"Q2545100"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109047$6F562275-412B-4823-82BD-3568671C4EA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a2ca07d50aa240b4ccbe9fedf2b4516f9bba12f","datavalue":{"value":{"entity-type":"item","numeric-id":2558871,"id":"Q2558871"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109047$AAE18520-72CC-40E4-8A3B-2043DD8371A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4873262ef1cd18bae17898f37af6fa8892a64114","datavalue":{"value":{"entity-type":"item","numeric-id":1161757,"id":"Q1161757"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109047$69DF50E2-BD18-435F-B3E1-0A8CC5AE895F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"31403449edcb685befef57967c6d318e33df55c0","datavalue":{"value":{"entity-type":"item","numeric-id":1247984,"id":"Q1247984"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109047$CBBD86D7-8F98-4A76-8A8D-0BF385E5F481","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"98e94f48f484608988ed586f06f8fbc5355f15ae","datavalue":{"value":{"entity-type":"item","numeric-id":5578810,"id":"Q5578810"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109047$AE71D68A-3289-4F95-A3BE-F04900555CB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5e83a22b3288989b0fa59340754b821b89f39f81","datavalue":{"value":{"entity-type":"item","numeric-id":2539388,"id":"Q2539388"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109047$7DBFBE7B-C655-441F-A342-6AF56143DC69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bb3b7fb38cb67438d9ac0e86da860270190ce82b","datavalue":{"value":{"entity-type":"item","numeric-id":774916,"id":"Q774916"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109047$20AA24CD-567D-4929-A173-49991ABA65FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2fda4b4f3f642da69f3574160a584d145f6434b0","datavalue":{"value":{"entity-type":"item","numeric-id":775674,"id":"Q775674"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109047$D756C1E5-6C4B-4C09-9208-17B27EB9AC76","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"85794c185aff365f23d72b87e9529f5533746bb6","datavalue":{"value":{"entity-type":"item","numeric-id":5722819,"id":"Q5722819"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109047$D249B0AD-B383-4614-A030-ED1470E5F67D","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"77df5ae7df523cc2fe0314586daf53e5594bb873","datavalue":{"value":"Q126819334","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109047$A356A7C3-C504-45FA-AE8F-F5B2F63255D6","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"4957bbefba9fdb47cd008c2d6e12143fbd146ae8","datavalue":{"value":"https://doi.org/10.1016/0012-365x(88)90069-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q1109047$A7D7EE5E-AAE6-4266-ADD3-5A862518D65A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ba54478fa0f4387b68e41cdf31c8806bde719fd3","datavalue":{"value":"W2038465558","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109047$0CF231AD-5CED-48E2-98A2-92F0A5E3CCAF","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e998b58856e5d5aa11a1284e467d911d94fcc38c","datavalue":{"value":{"entity-type":"item","numeric-id":384905,"id":"Q384905"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4bb913aab82a2071222a3292930be44831b08598","datavalue":{"value":{"amount":"+0.7906752228736877","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":"Q1109047$E5E26330-A97E-4EA3-8521-6A1728A18372","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"379bca67a60603392b56d8d07f3d2beffbafb1b6","datavalue":{"value":{"entity-type":"item","numeric-id":4780531,"id":"Q4780531"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"44e7edfae8d1350d2a90b8841f8fe42d85125c82","datavalue":{"value":{"amount":"+0.780904233455658","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":"Q1109047$2D824F04-D223-4741-9B0B-B19214F3C90B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"671e0318bac2cf5e52db762cac2b70f8ae826770","datavalue":{"value":{"entity-type":"item","numeric-id":3222879,"id":"Q3222879"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"316c903ffa410f08a5c21b7415f11224dbd3ed7a","datavalue":{"value":{"amount":"+0.773737907409668","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":"Q1109047$45A27631-379F-4B7E-B090-0CF00FBB1558","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e24ca5187174eba4dcf64d574f19fdb7541a5f4e","datavalue":{"value":{"entity-type":"item","numeric-id":2864296,"id":"Q2864296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"28cf6b659a0da819c9fdbd1e5258a0c12c768ed3","datavalue":{"value":{"amount":"+0.7674298286437988","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":"Q1109047$E555838B-A652-4027-A982-334A8F58F6B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4300b62c5fc502d910f690427aca665a047346ca","datavalue":{"value":{"entity-type":"item","numeric-id":2714911,"id":"Q2714911"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"47933336a8d6dd456a079c180a8b4b05740b3887","datavalue":{"value":{"amount":"+0.7665462493896484","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":"Q1109047$60B96ACD-BEA8-4332-8249-5DF663EA01B8","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Scattering number and extremal non-Hamiltonian graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Scattering_number_and_extremal_non-Hamiltonian_graphs"}}}}}