{"entities":{"Q1381845":{"pageid":1392585,"ns":120,"title":"Item:Q1381845","lastrevid":67505811,"modified":"2026-04-12T18:27:48Z","type":"item","id":"Q1381845","labels":{"en":{"language":"en","value":"Neighborhood conditions for balanced independent sets in bipartite graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1135955"}},"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":"Q1381845$5F0DEB6D-6694-44B6-BEE3-5D222CB684EB","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d529505fe7542d9560d95d7d39a7ce1467ba7178","datavalue":{"value":{"text":"Neighborhood conditions for balanced independent sets in bipartite graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1381845$6126C479-AD3F-42C2-9ED8-FC96DB6395EF","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4b0417d363241e9748aa1b7b7c7bceb444a80687","datavalue":{"value":"0890.05046","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1381845$815559EA-A371-4F1D-8B25-B30E33FE8AB1","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"5a8b4a91d5067cbf8bf762eb99c7ed1e56fd1daf","datavalue":{"value":"10.1016/S0012-365X(97)00042-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1381845$789A4C27-F754-479C-8943-01F67160E582","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5575f19c3f7fb2e8616fb8b613c936e212e4d98a","datavalue":{"value":{"entity-type":"item","numeric-id":237408,"id":"Q237408"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1381845$F66908BB-3017-42F2-ACA8-D5FBF7ACE28E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"35fe75700063d91d5aa0430b9cbc603605f8dc13","datavalue":{"value":{"entity-type":"item","numeric-id":383768,"id":"Q383768"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1381845$3F61A593-592A-43C6-9996-E8116D8678CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f14fc42ce922b80ab6fa7e1116a6c53c482b14ed","datavalue":{"value":{"entity-type":"item","numeric-id":1381844,"id":"Q1381844"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1381845$A482CC1B-A71C-4627-A147-28DCC1830145","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"5eca24ee3a318f34902b1cc98d15847bf80a0633","datavalue":{"value":{"entity-type":"item","numeric-id":195166,"id":"Q195166"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1381845$C7C798C8-5314-45D4-B325-E1C87B2C0E12","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":"Q1381845$5ECCA5E7-5CE0-4B1B-8EB0-5370BF8B6716","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7a4aa9887492d0c8972f96f0b793034d2ed1a547","datavalue":{"value":{"time":"+1998-06-22T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1381845$D86F82B8-53E6-4A9C-A010-5260B39A7558","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"fbb0d55a3c104a79008e781a5029706899c0e22e","datavalue":{"value":"Let us assume that \\(\\Gamma\\) is a balanced bipartite graph (i.e., \\(\\Gamma\\) admits a bipartition into two independent vertex sets with the same cardinality) of order \\(2n\\) in which all valences are \\(\\geq3\\). We assume further that the neighborhood \\(N(S)\\) of any independent 4-subset \\(S\\) of \\(V(\\Gamma)\\) consisting of two vertices from each side of the bipartition satisfies \\(|N(S)|>n\\). In this clearly-written, well-motivated, example-rich paper, the following conclusions are deduced: \\(\\Gamma\\) is either Hamiltonian or contains a spanning subgraph consisting of a cycle and an isolated edge; \\(\\Gamma\\) is traceable; \\(\\Gamma\\) either has a 2-factor or belongs to a small subclass of examples in which \\(n=7\\).    It is conjectured that under the above assumptions, \\(\\Gamma\\) is Hamiltonian or belongs to this small subclass. By sharpening the inequality to \\(|N(S)|>n+2\\), the authors show that \\(\\Gamma\\) is in fact Hamiltonian.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1381845$88BA66B9-702D-4C2C-9FE2-289D6B748677","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"eef1b49f4a66afb755b22d7419db9d61ba07415f","datavalue":{"value":"05C45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1381845$8BF05195-4E48-4837-85F5-CEB409881E7E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1381845$7F9F6670-E5B8-4589-83D4-954E83A23C26","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1381845$FCC2C2A1-8F6C-4A56-B794-F4000906647A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5554b9c844f173ce8299bcb1bb0c8b42f6b4a0be","datavalue":{"value":"05C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1381845$F36DD10D-C805-431F-A7DB-1ED79D4083B7","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e52efb9551bd09451defbc8f164e0c207b13ce7c","datavalue":{"value":"1135955","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1381845$44D957E4-AE61-432B-BB5F-772E50FB4F9B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c822c54638e4070b56aee42666fe01efcdddece8","datavalue":{"value":"Hamiltonian","type":"string"},"datatype":"string"},"type":"statement","id":"Q1381845$024788AF-EAEA-4DD6-94F2-093C32FB9B34","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e3835ecf46185b926af442cc2b7ac4fafe7516d2","datavalue":{"value":"neighborhood union","type":"string"},"datatype":"string"},"type":"statement","id":"Q1381845$8B1D0936-089D-405F-823C-DAB180064FD3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3187e84c5efaed03d0bd9515713a70084404d3ee","datavalue":{"value":"bipartite graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1381845$292CBB94-F5FD-454D-9391-757B791C03EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a36f1f661169e98576879579295ecf0220457b9c","datavalue":{"value":"independent set","type":"string"},"datatype":"string"},"type":"statement","id":"Q1381845$0A02EB12-24B4-4937-89F7-389C3B821223","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1b192458bf3e522f8d2259357613260c470fc9a0","datavalue":{"value":"traceable","type":"string"},"datatype":"string"},"type":"statement","id":"Q1381845$DAED1353-3CC2-4397-97AB-660145C26412","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"19ec132a1ede33f50fb04fa222303f9cda249a50","datavalue":{"value":"perfect matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q1381845$1DE271F6-F057-4791-9C5A-C3030CE402B4","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"2420d8bcf60fc74d0291a3c59f694629f273e260","datavalue":{"value":{"entity-type":"item","numeric-id":426905,"id":"Q426905"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1381845$F1821889-43BB-489B-9A71-9D3D5DCAF1D2","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":"Q1381845$4A408E56-1304-429C-BC19-E148540EC170","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f091a2487faa4320a607c7fc5ddd1d40ffc78957","datavalue":{"value":{"entity-type":"item","numeric-id":5615282,"id":"Q5615282"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1381845$BF8CC150-0E5E-4AD2-86E0-1171977C6001","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c678a4d607ee7c59493765993ec168741685091b","datavalue":{"value":{"entity-type":"item","numeric-id":1313847,"id":"Q1313847"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1381845$122BB048-BF4C-4326-9C03-4AE3EE130331","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"561c7ce8c27e20759a236fb466d62fec73eb38f5","datavalue":{"value":{"entity-type":"item","numeric-id":1123212,"id":"Q1123212"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1381845$A06325E8-4064-4D5E-9A8B-463B206C710A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6552cc85a61490eb3f50fd663ed958a48555f4a3","datavalue":{"value":{"entity-type":"item","numeric-id":3980626,"id":"Q3980626"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1381845$765094C6-002E-4F16-9A14-E005D4DF45B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"437ebe0c1320329dc48bb92b41d79db15821185e","datavalue":{"value":{"entity-type":"item","numeric-id":2626464,"id":"Q2626464"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1381845$85E4693C-B079-492A-8173-42E31AA3BDF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"46a8bc768737525dbe4a8a14511050065fb6cde8","datavalue":{"value":{"entity-type":"item","numeric-id":5605171,"id":"Q5605171"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1381845$6A94D0B0-AC95-4E2F-80FE-4018EA470C19","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d2e193ba09c385c8f01e565c48dcfebfbfad6485","datavalue":{"value":{"entity-type":"item","numeric-id":4895662,"id":"Q4895662"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"74648adf32eb677aa22fcc6cabbbf68a131f93ea","datavalue":{"value":{"amount":"+0.8852423429489136","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":"Q1381845$0E9A366A-0BD2-45B0-9125-A94F2A1099A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"40312c4e30cf528c75dbb485d54a9733b72fda6a","datavalue":{"value":{"entity-type":"item","numeric-id":3073889,"id":"Q3073889"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2e58550105f987974bcc18b9d846b2aea44fbc4d","datavalue":{"value":{"amount":"+0.8646883964538574","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":"Q1381845$2D79E5EC-3543-4C0C-A573-272F3541634D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6368783003effca836875ed0a71454b24a5e9873","datavalue":{"value":{"entity-type":"item","numeric-id":5402083,"id":"Q5402083"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"efc30d01f842952c5b216499f06fc9f3dd9f3678","datavalue":{"value":{"amount":"+0.8601746559143066","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":"Q1381845$6FEF21B5-7796-4546-90D2-A042CB6E64C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1fafae96130175d4ae0e24e8f288204e7081d732","datavalue":{"value":{"entity-type":"item","numeric-id":1356424,"id":"Q1356424"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"371972530ddd8a0103621fa0734933d851b7bcda","datavalue":{"value":{"amount":"+0.8261058330535889","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":"Q1381845$64A712DB-0EDA-453C-BC80-8C03C3A6DDC6","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Neighborhood conditions for balanced independent sets in bipartite graphs","badges":[]}}}}}