{"entities":{"Q2366217":{"pageid":2376960,"ns":120,"title":"Item:Q2366217","lastrevid":78676763,"modified":"2026-05-06T12:10:35Z","type":"item","id":"Q2366217","labels":{"en":{"language":"en","value":"Gadget classification"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 223447"}},"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":"Q2366217$CFA53E86-EAA3-4186-B05A-26982F9ACC6B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a0436fdb96ade045ae23c16fcd3c2beeaa3d8974","datavalue":{"value":{"text":"Gadget classification","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2366217$A2A35F7D-255D-4F99-BBEE-72D636FEB666","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2fc03bef9e81f8c8642e88879446ce20957d9f4a","datavalue":{"value":"0778.05066","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2366217$7970433A-C8BA-4235-B6DF-06E556E4DAA1","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"be46da4dfc9d2caf454f6c1a4933f801be70ffc4","datavalue":{"value":"10.1007/BF01195327","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2366217$AC031515-3590-47B1-B911-81DEBBB92763","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"62093226388c211ee4d5286124caf1fbc8b86437","datavalue":{"value":{"entity-type":"item","numeric-id":185060,"id":"Q185060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366217$CBAE77EB-3BA8-40E5-9DA1-777C993AC518","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"be4381b75afe2df0dbe37cd1a66e006418c0c5aa","datavalue":{"value":{"time":"+1993-06-29T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2366217$AECED72F-3263-459A-A8B9-FAEFC1FA489F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ac1e76d0efb0625514549d0fdf2af6eb75a5b1cc","datavalue":{"value":"Let \\(G\\) be a graph and, for each vertex \\(v\\), let \\(B_ v\\) be a set of integers between 0 and \\(\\deg_ G(v)\\). A \\(B\\)-factor of \\(G\\) is a spanning subgraph \\(H\\) with each \\(\\deg_ H(v)\\in B_ v\\). To decide the existence of \\(B\\)-factors is NP-complete in general, but polynomial if no \\(B_ v\\) contains a gap of more than one element (cf. \\textit{L. Lov\u00e1sz} and \\textit{M. Plummer} [Matching theory (1986; Zbl 0618.05001)] and \\textit{G. Cornuejols} [Carnegie Mellon Management Science Research Report MSRR 528 (1986)]. It was observed by Pulleyblank that for certain restricted types of \\(B_ v\\)'s, the problem of existence of \\(B\\)-factors can be reduced to another factor problem---that of finding a spanning subgraph of a given graph in which all components are either edges or triangles (from a given family of triangles). This problem is known to be solvable in polynomial time, cf. \\textit{G. Cornuejols}, \\textit{D. Hartvigsen} and \\textit{W. Pulleyblank} [Oper. Res. Lett. 1, 139-143 (1982; Zbl 0488.90070)], or \\textit{P. Hell} and \\textit{D. G. Kirkpatrick} [Algebraic methods in graph theory, Vol. I, Conf. Szeged 1978, Colloq. Math. Soc. J\u00e1nos Bolyai 25, 273-279 (1981; Zbl 0474.05054) and Discrete Math. 49, 45-59 (1984; Zbl 0582.05046)]. The `gadgets' in the title of this paper refer to the modules used in that reduction. Pulleyblank asked exactly which sets \\(B_ v\\) allow such a reduction, i.e., admit a gadget. Cornuejols found this to be the case if \\(B_ v\\) has no gaps (the set is an interval of consecutive integers) or if the gap is just the second element (or the next to last element) of an interval. The present author shows that this is so also if \\(B_ v\\) is an interval with both the second and the next to last element removed; he also shows that gadgets do not exist for any of the other types of sets \\(B_ v\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2366217$AFF315A8-F233-458C-A7BD-A3401B0837CE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2366217$A5927A9F-981B-4B75-8DCD-CDFA8A8655D5","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"da0a5ff40cdaac4b05476feb1b76549b4db58f4f","datavalue":{"value":"223447","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2366217$878DE178-AF44-452D-BC4D-E544EF8ED82E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f12eb165bd6cb53df1cbde83765cb1c65a6033d","datavalue":{"value":"classification","type":"string"},"datatype":"string"},"type":"statement","id":"Q2366217$1FFB6646-D431-4840-94D5-4E1CEEF2748C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ce4676d4560667e737e972fc782282a8d634574d","datavalue":{"value":"factors","type":"string"},"datatype":"string"},"type":"statement","id":"Q2366217$F35BB768-ECD9-412F-9915-690D2DD2D802","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3bcb88e4835cfef6b70b1d60481bd40424864103","datavalue":{"value":"spanning subgraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2366217$FF032174-EC49-41A8-A08C-F0FAC13EC019","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q2366217$71555217-2193-4DB5-BE07-3E9D0F3732D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"accdd20e28d3630914003f8053fb711b2bae3a8b","datavalue":{"value":"triangles","type":"string"},"datatype":"string"},"type":"statement","id":"Q2366217$7BDA9743-955F-4052-8E3F-AB2AB56ADE38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"291b24e9a82e4d95a1b477fdec833d63391e3282","datavalue":{"value":"gadget","type":"string"},"datatype":"string"},"type":"statement","id":"Q2366217$F1444B5E-6662-4F1C-9829-D4F09B7D8A09","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6e288ae08772fffcadfa65aedce51f2b962364fd","datavalue":{"value":{"entity-type":"item","numeric-id":185366,"id":"Q185366"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366217$5A77C704-A732-46A7-8F5F-0C43B989A812","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"cc7e193006699e29b5b5a77a1be6eeba002bc504","datavalue":{"value":{"entity-type":"item","numeric-id":338573,"id":"Q338573"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366217$FAD5A5D4-F8C2-4120-93EE-10337F0F2A9E","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":"Q2366217$755FAA52-9811-443B-B290-526792269B62","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"3de7edad0b76fa41f3d5b9d1b0f37d5e44dc7a8a","datavalue":{"value":{"entity-type":"item","numeric-id":1166429,"id":"Q1166429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366217$320EED52-3266-4D40-A5AE-B3AF9CB05C96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366217$ADC971A6-6F07-416F-A36A-617831C50AF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7f3e2cdfb6fc77f978ebc89ff0887a2b1da2a777","datavalue":{"value":{"entity-type":"item","numeric-id":1109053,"id":"Q1109053"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366217$9921BCDE-C6C0-4F4C-9745-1C7DD353DC41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"39d9c16f8523a607dda3d616da31f4b98b772697","datavalue":{"value":{"entity-type":"item","numeric-id":3478438,"id":"Q3478438"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366217$368ADDBE-EDE2-4BD6-96D8-9F1E7DF91A15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c00bceff6f60fb60810dddb1bd6a2b2ff394b899","datavalue":{"value":{"entity-type":"item","numeric-id":5595084,"id":"Q5595084"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366217$07B74627-3597-4002-B466-750D8976FF19","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b9a3ada332d9b1d8bf5360191802e9e5d56978f0","datavalue":{"value":{"entity-type":"item","numeric-id":5659592,"id":"Q5659592"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366217$9692278C-4075-4723-8B0C-028280781704","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a4969d6a80ed53fd7ef27bdf261cf43fcb201bac","datavalue":{"value":{"entity-type":"item","numeric-id":1393414,"id":"Q1393414"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366217$6ADD4072-5841-4CA1-9523-837F799EC28A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"33db1290af320389a57e729a8a4182433f7a0cb8","datavalue":{"value":"https://doi.org/10.1007/bf01195327","type":"string"},"datatype":"url"},"type":"statement","id":"Q2366217$F274C706-6E75-4118-A09A-852E6AE6567B","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"fa298b67997cedeaf86afff0cb5d12652c5f44df","datavalue":{"value":"W4234565540","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2366217$566CB8E3-812D-40F7-B9B3-C30CA7E57D9B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ab1a2c160fa0a0643b6b8e9180c39b5d48f42864","datavalue":{"value":{"entity-type":"item","numeric-id":1085185,"id":"Q1085185"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"38142b1a5bdf177df025cb161dc5187dfd6f4d25","datavalue":{"value":{"amount":"+0.7942456603050232","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":"Q2366217$01DA0A0B-5BD3-415A-AC27-542D0C4B7C9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c37c4e7e9f350bfb4911f3c076f80643ae5d553d","datavalue":{"value":{"entity-type":"item","numeric-id":1003846,"id":"Q1003846"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1cddc4d4213ff3a5dabea5f18f1be37b10ee9e12","datavalue":{"value":{"amount":"+0.7575040459632874","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":"Q2366217$2A76AF93-BDC5-49DE-977E-AA306777EF4E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"858137aeb863afb9baea8d79e2b73354fe738ec9","datavalue":{"value":{"entity-type":"item","numeric-id":3825107,"id":"Q3825107"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"110ea46d4bc6f1c9f673570bec8a36fb48ec8be7","datavalue":{"value":{"amount":"+0.7571795582771301","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":"Q2366217$6A3EA227-5989-4E2E-89AC-812CDF29151C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0f3ac642199fd58781a48484c988c19a23786f03","datavalue":{"value":{"entity-type":"item","numeric-id":3728943,"id":"Q3728943"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c4f520e974c427a21bd80e1112a42af364bf57ed","datavalue":{"value":{"amount":"+0.7565274238586426","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":"Q2366217$5DFF1F71-BE0D-4763-B020-2374B3C41BC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6ca64fc86aec5e5a5e47069468b6ee59b8ef3194","datavalue":{"value":{"entity-type":"item","numeric-id":1193724,"id":"Q1193724"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"92982f88d61a127dab550ba5f27efef00aa3b38c","datavalue":{"value":{"amount":"+0.7438321709632874","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":"Q2366217$FE690BF9-C9FF-4818-A7F5-C48BA06326A4","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Gadget classification","badges":[]}}}}}