{"entities":{"Q810050":{"pageid":811898,"ns":120,"title":"Item:Q810050","lastrevid":64544373,"modified":"2026-04-11T20:36:46Z","type":"item","id":"Q810050","labels":{"en":{"language":"en","value":"Solution of two problems of P. Erd\u0151s concerning Hamiltonian cycles"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4212092"}},"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":"Q810050$F94827E3-F7C3-41DF-BB1B-6E7EA42815B9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2da6f91940eac3b58784a0a4ab903a746353f66d","datavalue":{"value":{"text":"Solution of two problems of P. Erd\u0151s concerning Hamiltonian cycles","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q810050$0CE24DD0-46BB-4F61-B2B9-E75DCD6A3C64","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f2e66f947e52a103a57a99e9328baabe414b2ad7","datavalue":{"value":"0733.05054","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q810050$341C1D6A-2462-4113-9C95-9480F19163D8","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6ca3ead5127dfda8034b1800bb4839b4ac798159","datavalue":{"value":"10.1016/0012-365X(90)90269-N","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q810050$B94E7F35-3D5B-495C-B65F-154E2B3E7CDF","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c4d93fa0730cf967b4d44ea1e6c1e65e24d47c8c","datavalue":{"value":{"entity-type":"item","numeric-id":175610,"id":"Q175610"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q810050$5AAC3DA0-2C52-4C2B-A4FA-BB8FA1A089F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e71d1531addd3e751a7c2f29dcec31264ed06413","datavalue":{"value":{"entity-type":"item","numeric-id":215558,"id":"Q215558"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q810050$DB92798F-0DBE-468B-A779-30A03F1068FB","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":"Q810050$55C85B5E-81E7-4728-91D7-ED4F761FE2DD","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"70d2fbf8bcd48a5ca1ac752985098b379d0dbb65","datavalue":{"value":{"time":"+1990-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":"Q810050$2BFB3336-451A-487C-9D62-58862835A05C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"963dc1b1169a04d2a332e9197ce3b777c30899fd","datavalue":{"value":"The graphs \\(G_ 1,G_ 2,...,G_ r\\) are packed into \\(K_ n\\) if \\(K_ n\\) has edge-disjoint subgraphs \\(G_ 1',G_ 2',...,G_ r'\\) such that \\(G_ i'\\cong G_ i\\). Suppose we consider packing graphs into \\(K_ n\\), requiring each to be a graph on n vertices with a non-Hamiltonian complement. Regarding the packing of such graphs, P. Erd\u0151s posed two problems:    (1) What is the maximum number g(n) which can be packed into \\(K_ n?\\)    (2) What is \\(f(n,r)=\\min \\sum^{r}_{i=1}e(G_ i)\\), where e(G) is the number of edges of G and the minimum is taken over all r-tuples of graphs packed into \\(K_ n?\\)    The paper provides a solution to each question. It is shown that \\(g(n)=3+_{\\lfloor}\\log_ 2(n-1)/3_{\\rfloor}\\) for \\(n\\geq 4\\). In connection with (2) it is known that for any graph G with non-Hamiltonian complement, there corresponds a number t(G) counting the number of vertices of a certain degree. An expression for f(n,r) is obtained in terms of a function of such t(G). The proofs exploit the properties of a particular collection of extremal graphs which can be packed into \\(K_ n\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q810050$6AEE3D35-A86F-4F88-9F65-74BA0275A30F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q810050$97FE7111-5DD3-4912-92E9-7E667E8FEA74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"eef1b49f4a66afb755b22d7419db9d61ba07415f","datavalue":{"value":"05C45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q810050$0DCD7751-81A8-463D-BA82-98E68EBC2A37","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q810050$041801D9-92B6-4A56-8BD5-AC910371F592","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"922aedaa4e4b7b1d7c32444a42ef622b1b5c0a9b","datavalue":{"value":"4212092","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q810050$D2869707-7514-4C71-B24B-91A46A3F4C46","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"093ef3cbea03ec661dc66ae3009ad13581b7249b","datavalue":{"value":"packing","type":"string"},"datatype":"string"},"type":"statement","id":"Q810050$F8835FC0-DCEC-408C-9370-AA77DC3046BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"26cc3fab0ffe68da8ef55fc40e0116487e131b5a","datavalue":{"value":"non-Hamiltonian complement","type":"string"},"datatype":"string"},"type":"statement","id":"Q810050$D55C3FA3-E708-475C-8170-66C9E99F1A3C","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"bf8837edd6f8e1022b15c3d0748921656854f53e","datavalue":{"value":{"entity-type":"item","numeric-id":1811077,"id":"Q1811077"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q810050$5285A742-3FC9-4DD0-B596-4F45BCEB21F8","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":"Q810050$3BEE1237-15B2-46B9-9597-4DBF9A145C6C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"9c743424de859b331f95293d9a28c4c6a188a467","datavalue":{"value":{"entity-type":"item","numeric-id":5722820,"id":"Q5722820"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q810050$06210634-313C-42BC-BAAF-649B800B0AF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c0c30ed7f4657a40586bae0b4871c8f350147d07","datavalue":{"value":{"entity-type":"item","numeric-id":1077429,"id":"Q1077429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q810050$589407BE-0F2C-4C2C-B0DD-20DE25211AEA","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":"Q810050$190B8178-785E-4F71-B8C3-E090A2040F9E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"83554d762de9ff780018f9c9f152c44e98f9c88c","datavalue":{"value":"https://doi.org/10.1016/0012-365x(90)90269-n","type":"string"},"datatype":"url"},"type":"statement","id":"Q810050$102E4F79-21E7-4B15-A35F-4CFD3F13FCEA","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"3eab428408207c3f98289521638b4b7940fb942a","datavalue":{"value":"W1966215030","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q810050$38521EA0-6E2D-4132-843C-72532F242B41","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1f646f175bb0ad06cd3e4509fe4b48579bb92519","datavalue":{"value":{"entity-type":"item","numeric-id":3715141,"id":"Q3715141"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"05d484e889f4efc772f7e455c192d8b54d3ae0b2","datavalue":{"value":{"amount":"+0.91911906","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q810050$39B0BFD1-7E24-49A4-BEE0-18A156F6F8A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d54b8f4a1c6e3e860d013f7ae6b8ac4da0a1b018","datavalue":{"value":{"entity-type":"item","numeric-id":326810,"id":"Q326810"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"91448108bc5709e8ddba4f3e84a0d5d0a334865c","datavalue":{"value":{"amount":"+0.9137319","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q810050$90981CEA-F010-4609-A8F8-1260976D97D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f3e3ffc9454cdf504a383f1858cda62c206cbffc","datavalue":{"value":{"entity-type":"item","numeric-id":6165143,"id":"Q6165143"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0b1631b18daed64b92421993925ef17a7eae5d85","datavalue":{"value":{"amount":"+0.90870845","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q810050$C1221085-4F87-457B-9FF9-9E7718E46837","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2a37a6064f1598e52e017425055dd63efdcadb39","datavalue":{"value":{"entity-type":"item","numeric-id":1010935,"id":"Q1010935"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ad14f5d058a68df4b4b3c1d56ad9785d644b6b63","datavalue":{"value":{"amount":"+0.90179443","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q810050$BE4E6053-BF45-4559-BA1F-BB8473B949A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f53034202516aec1b54718cdb24aedc66c3fbd05","datavalue":{"value":{"entity-type":"item","numeric-id":1900521,"id":"Q1900521"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a3e855bda9a726f19cdfb6038576c7df4a5cbb95","datavalue":{"value":{"amount":"+0.9016867","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q810050$F9A5AE30-0B5D-4028-88B9-B7C28509715D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"964f1e7dc95bc5b27603468ed25f47d27ffa2f62","datavalue":{"value":{"entity-type":"item","numeric-id":4378246,"id":"Q4378246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"034d829b736c987ddadc7961b0d7976b37e574e0","datavalue":{"value":{"amount":"+0.8972184","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q810050$EF7A86C7-AC24-4A53-9FFF-8C03D644247C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eeb682cc943115e4db19b7d7825f8c6ab4334388","datavalue":{"value":{"entity-type":"item","numeric-id":3980663,"id":"Q3980663"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"16e9e3e178b289de2e8341546c79d860e24b0c08","datavalue":{"value":{"amount":"+0.8956637","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q810050$263C78AE-093C-46FE-B020-BC768E95B600","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"28102ce3e9461f4b5efa74759cf5ea5219701dc0","datavalue":{"value":{"entity-type":"item","numeric-id":3309913,"id":"Q3309913"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"57de90f1a96412a65cffbe411161be70b549537c","datavalue":{"value":{"amount":"+0.88584775","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q810050$5F4FC8FF-2843-4DC4-98C0-5A7BC143106F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"04841948fb0c4e4680c3701b8dd37023b5caec48","datavalue":{"value":{"entity-type":"item","numeric-id":3469119,"id":"Q3469119"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5826a6ffe9f560accf5b79bc5bfdeabf5c23ff96","datavalue":{"value":{"amount":"+0.8855017","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q810050$B2495F60-2DE8-495F-B17A-8718C28B1BDA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d3fa0e634fa5b734bca1a8bf912c2defe6222ae9","datavalue":{"value":{"entity-type":"item","numeric-id":4304421,"id":"Q4304421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cab8612535f005a67063980940f3e57ebc883f66","datavalue":{"value":{"amount":"+0.8832083","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q810050$BE1DF6EA-93E5-48CF-B252-CD480F418B6B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Solution of two problems of P. Erd\u0151s concerning Hamiltonian cycles","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Solution_of_two_problems_of_P._Erd%C5%91s_concerning_Hamiltonian_cycles"}}}}}