{"entities":{"Q1112064":{"pageid":1122813,"ns":120,"title":"Item:Q1112064","lastrevid":67031805,"modified":"2026-04-12T14:26:51Z","type":"item","id":"Q1112064","labels":{"en":{"language":"en","value":"Contractions of graphs with no spanning Eulerian subgraphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4077270"}},"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":"Q1112064$A4CC2A4E-060D-4C25-971F-F5E98304F054","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b4e79584c14ead81c6ccd7ade516ffb3780ba7c6","datavalue":{"value":{"text":"Contractions of graphs with no spanning Eulerian subgraphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1112064$95A06C66-E42B-42DF-8DE5-00F0066B454E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6d17a98abe2e84ecdde609a95e141e4d16b117cb","datavalue":{"value":"0659.05064","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1112064$DB69A7A6-A786-43AB-8B99-1F44817983DB","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6930411271127c22d64f57cf98c373342a16fd98","datavalue":{"value":"10.1007/BF02189088","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1112064$1833F086-A079-4DA6-A2D0-4EDE9C329EEE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6a5c65629bb824e3a2f06c4cadc138dc32994e68","datavalue":{"value":{"entity-type":"item","numeric-id":175501,"id":"Q175501"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112064$B5308D5E-356D-4097-A565-F28AF2223F9F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112064$1017A920-399E-4A88-9681-237141D66746","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":"Q1112064$3425409B-0337-43F0-B7B1-C8BC2BD0EDED","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d1bdc7293761bed0a2d7a707bf020a62f066966c","datavalue":{"value":"The concept of collapsible graphs introduced by the author in J. Graph Theory 12, 29-44 (1988), is here used to study the existence of spanning Eulerian subgraphs. The following result is given: Let \\(p\\geq 2\\) be a fixed integer, and let G be a connected graph of order n. If \\(d(u)+d(v)>2n/p-2\\) holds whenever uv\\(\\not\\in E(G)\\), and if n is sufficiently large compared to p, then either G has a spanning Eulerian subgraph, or G is contractible to a graph G' of order less than p and with no spanning Eulerian subgraph. The case \\(p=2\\) was proved by \\textit{L. Lesniak-Foster} and \\textit{J. E. Williamson} [Can. Math. Bull. 20, 215-220 (1977; Zbl 0357.05060)]. The case \\(p=5\\) was conjectured by \\textit{A. Benhocine, L. Clark, N. K\u00f6hler} and \\textit{H. J. Veldman} [J. Graph Theory 10, 411-425 (1986; Zbl 0608.05056)] when they proved vitually the case \\(p=3\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1112064$7EF178FE-E712-483D-8E5F-C3B11BA4E354","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"eef1b49f4a66afb755b22d7419db9d61ba07415f","datavalue":{"value":"05C45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1112064$6B0283D5-3C09-4F1E-957E-7B3F3E2D7473","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ece4de278cb07d5855bd2058b437cdb32779922d","datavalue":{"value":"4077270","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1112064$989E384E-7B27-4532-A315-6CEFB80669AE","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"795f3a85973535c1093acee8b74de638a4bc8de4","datavalue":{"value":"collapsible graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1112064$15DA9B9C-A44A-4707-B499-8E9FE170592B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f7c74d77d09e873a4bf42394581036b47c9e3b72","datavalue":{"value":"spanning Eulerian subgraphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1112064$4B938C65-ADED-4E03-AEBC-7E3DA9676476","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":"Q1112064$B8A75BA3-B752-420D-AD23-0EDEE4B0C3BD","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"7a90d7705154eb307e4ca3a2d75e813bbdfb05fb","datavalue":{"value":{"entity-type":"item","numeric-id":3748308,"id":"Q3748308"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112064$9108F1F6-75F7-4893-9263-B94FFA81A885","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ec43697f55d2831260531dc3a703daec7e48dc6e","datavalue":{"value":{"entity-type":"item","numeric-id":1124608,"id":"Q1124608"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112064$1F2D65BA-BA87-4D13-8ABB-4FF366C18886","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"78142425e57f895e472d8c08743c5cc9791af2e9","datavalue":{"value":{"entity-type":"item","numeric-id":5509542,"id":"Q5509542"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112064$E7905E81-D559-4658-BBCC-8F135737487C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dd818ade1d68346387b4e1eeca1812aa42afd7b0","datavalue":{"value":{"entity-type":"item","numeric-id":4179046,"id":"Q4179046"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112064$A17DE002-A7E4-457E-902A-193AE8B82C8A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f429615e89dd3d1e870167e9cf4826e34d407381","datavalue":{"value":{"entity-type":"item","numeric-id":4129479,"id":"Q4129479"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112064$039093A9-0082-423D-8B1B-350D402A88C1","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ccca0b39ed9e572058f745ed8b2a311fa68527e2","datavalue":{"value":"https://doi.org/10.1007/bf02189088","type":"string"},"datatype":"url"},"type":"statement","id":"Q1112064$2DE9AFC2-D4F7-4CF5-A71B-B4EBBA4E6E49","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"412a1c05ed24c1668186358a607bd3bd7c9665d3","datavalue":{"value":"W1997421716","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1112064$8D9DF393-53BC-46B3-AAC8-6B5DE9748B6B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e9ab264745ead303d295366757ccef7ac3ce6de7","datavalue":{"value":{"entity-type":"item","numeric-id":1124608,"id":"Q1124608"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1fa91bcdf54606355196ae8ea85841e3bda3e1d0","datavalue":{"value":{"amount":"+0.8610551357269287","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":"Q1112064$9DB27517-A8AE-4EB8-A610-07BC2EFD3053","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"879c44142cb85b6a18b8fd0148b6c52691b82d10","datavalue":{"value":{"entity-type":"item","numeric-id":4693340,"id":"Q4693340"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"798e37542db5806aa98c90acd665038977826886","datavalue":{"value":{"amount":"+0.8578413128852844","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":"Q1112064$4075E183-D492-4B3A-9619-D391F8870EEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"89a7b6982f85f5783cf69113faeb69440ffca596","datavalue":{"value":{"entity-type":"item","numeric-id":3976604,"id":"Q3976604"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c486991cef5bb38c642a032f72bf79a773a9c621","datavalue":{"value":{"amount":"+0.8575546741485596","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":"Q1112064$BB99299A-2D5C-40A2-B82A-926387435E58","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9c7f0d69bb6f67968219187379414ee2a66b98ad","datavalue":{"value":{"entity-type":"item","numeric-id":3808126,"id":"Q3808126"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a6392a32f0e78d8908d428e164ea76fe539571f7","datavalue":{"value":{"amount":"+0.832835853099823","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":"Q1112064$938500E9-AAFB-4472-97D3-0318351F0AE9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"82e4711602e4b368d81755a7bbbf57e9ae5e4387","datavalue":{"value":{"entity-type":"item","numeric-id":5276339,"id":"Q5276339"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"35557f54f62ec729ba56f3ad1caa3ed72666905b","datavalue":{"value":{"amount":"+0.8262572288513184","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":"Q1112064$F1E9F906-428B-4224-9AAF-729A2BBF6C35","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Contractions of graphs with no spanning Eulerian subgraphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Contractions_of_graphs_with_no_spanning_Eulerian_subgraphs"}}}}}