{"entities":{"Q1322291":{"pageid":1333041,"ns":120,"title":"Item:Q1322291","lastrevid":70136259,"modified":"2026-04-13T12:41:31Z","type":"item","id":"Q1322291","labels":{"en":{"language":"en","value":"Graphical decompositions"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 562679"}},"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":"Q1322291$BCE2E387-B161-4045-9083-E172852E2BDB","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b9970462acba0be3d2b92f5fc6e16edc2319c300","datavalue":{"value":{"text":"Graphical decompositions","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1322291$67971452-AE9E-4678-9D44-62223FD1D015","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d14f083ee64b79e0a68971f8fa941bb93e6cfa11","datavalue":{"value":"0795.05079","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1322291$92AE384D-1E14-4996-969F-13C66236A446","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"97b42a320a4fceb1e91c8d624521c0e0f35b6137","datavalue":{"value":"10.1016/0012-365X(94)90176-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1322291$3E2E6198-25C5-4C47-AF55-7FAC49838568","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":"Q1322291$9BB261C3-1184-4049-BD0A-702F4A949622","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ae4d7b05535bc7692a75fc587d4810a7bdebded5","datavalue":{"value":{"time":"+1994-05-05T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1322291$557F86A0-85D4-41DB-BB2A-D690AB8A1ADD","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ff9a1c5e75be4f88e11966d5eefbfc61a330bc82","datavalue":{"value":"Suppose the vertices of the \\(k\\)-regular connected graph \\(G_ n\\) can be partitioned into two sets \\(X\\) and \\(Y\\) such that all vertex-degrees in the subgraphs induced by \\(X\\) and \\(Y\\) are at least \\(\\lceil k/2 \\rceil\\) and \\(\\lfloor k/2 \\rfloor\\), respectively. Let \\(W_ k(G_ n)\\) denote the minimum value of \\(\\| X |-| Y \\|\\) over all such partitions of the vertices of \\(G_ n\\) and let \\(W_ k (n)\\) denote the maximum value of \\(W_ k (G_ n)\\) over all such graphs \\(G_ n\\). The author obtains the value of or upper bounds for \\(W_ k (n)\\) for \\(1 \\leq k \\leq 7\\) and \\(n\\) sufficiently large, among other things. For example, he shows that \\(W_ 7(n) \\leq (17n + 356)/33\\) if \\(n \\geq 24\\) and \\(n\\) is even.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1322291$A6F804DE-D493-4304-B667-0328A5111BA4","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1322291$66D6D1F7-EE97-49AC-B9B3-B98AB408B05F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"63ccf0dd70546916b60b2ccaebb4e173cf6fc189","datavalue":{"value":"562679","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1322291$7F37B91A-F91F-46AF-B2AB-BCA7F93C9C0D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d3b8ff0cbe516a811721aeecd3743abd90abe53a","datavalue":{"value":"graphical decompositions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1322291$967B04AE-35CC-458A-806E-0EA97E9CE4BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c2675f10a67151be7538ce8d4107198cfb31554e","datavalue":{"value":"vertex partitions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1322291$01CE421C-D76D-454E-BFF1-100AD1EB53A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"34012c92c499b6a6beb6c6030b4f33ccbf9f4fcc","datavalue":{"value":"regular graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1322291$B985B531-E719-48CA-B997-2C27BDC25CD9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9b054bbd1ef16f604df0f61144322893e5b9a2a9","datavalue":{"value":"upper bounds","type":"string"},"datatype":"string"},"type":"statement","id":"Q1322291$04861001-6342-453A-92E4-12FA3BB8B4F7","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a10015d8dc84d50c1e5f084a7e3b6881a3686835","datavalue":{"value":{"entity-type":"item","numeric-id":420624,"id":"Q420624"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322291$3DF14352-D7FD-42FB-8F16-1E0F87024358","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"478bb984958f47159570b1788ede69358a5f4226","datavalue":{"value":{"entity-type":"item","numeric-id":656146,"id":"Q656146"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322291$C67676A9-4B27-4EA0-9363-E42650D645EA","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":"Q1322291$F3D43E95-8499-4461-B0ED-840BECDCF89E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f3aefaa1fe5faab12728571c48c13e5cfc1d90a2","datavalue":{"value":{"entity-type":"item","numeric-id":1242149,"id":"Q1242149"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322291$06A04A7B-C571-46D1-AFE3-C0C1473C6DCE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5f94b974a138f35ce7951b76f2590a33feac0733","datavalue":{"value":{"entity-type":"item","numeric-id":1053710,"id":"Q1053710"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322291$E1B109F7-037B-448C-908E-F72EF560AAFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"74074974e02935f8f5ecb942cc6fe70f08b746ea","datavalue":{"value":{"entity-type":"item","numeric-id":5530470,"id":"Q5530470"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322291$6F6D717B-133A-4E72-8618-49F7AE7C9E94","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6cf851998e815afd5a07ae43841ad6c7f4bc9bf2","datavalue":{"value":{"entity-type":"item","numeric-id":1235179,"id":"Q1235179"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322291$EF8F5FEA-320C-41A8-B630-6FC4768D54F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3d2d469031cb095740fc8da565f82a584d52adeb","datavalue":{"value":{"entity-type":"item","numeric-id":3737465,"id":"Q3737465"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322291$6225CA73-A8B5-4D51-A647-68DF4E50C99F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ada690442789d9f0c719cc23d581ec74cde90e16","datavalue":{"value":{"entity-type":"item","numeric-id":1102305,"id":"Q1102305"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322291$1F54D6EC-73E1-481F-99B3-05C6B30CA138","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5bd7f32eab95966047500859cec9b6f2f6f0b16b","datavalue":{"value":{"entity-type":"item","numeric-id":3970898,"id":"Q3970898"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322291$1B4BD9BD-A463-4ECA-BBC3-DF33C52A6862","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"74d28cc3d0131c6f700d78b9f4d53e9f87ffcd3b","datavalue":{"value":{"entity-type":"item","numeric-id":1193451,"id":"Q1193451"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322291$5C82D1A5-521C-416B-929E-F5CDCC28019B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ea8bc2ae23bb13dbcaf7cb2eeb2f5caf3d7d5489","datavalue":{"value":{"entity-type":"item","numeric-id":3661610,"id":"Q3661610"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322291$76D1A06C-4277-46D7-A8EB-B4DD7ECBBC6B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"027409ab786d464f82066d8ce58ea3ae45048b1e","datavalue":{"value":"https://doi.org/10.1016/0012-365x(94)90176-7","type":"string"},"datatype":"url"},"type":"statement","id":"Q1322291$30F64A1B-7F32-4627-8D2A-FD644789301D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ac068af7547bea9f8f358c6053e6060da5f16c7d","datavalue":{"value":"W2914963856","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1322291$779666E4-5942-431D-83E9-DF918E8D6FE8","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5801ad350cba81ee5f12687b111d3bd9703f4352","datavalue":{"value":{"entity-type":"item","numeric-id":3983103,"id":"Q3983103"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7e046cb2c7a047824bf87e0618c3e6bb505f0722","datavalue":{"value":{"amount":"+0.9672012","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1322291$9486AC42-AFC1-4496-B136-D46885C98DFE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"79c295b81ef67f4fa1ab1fc523fdbb75d99e1fcd","datavalue":{"value":{"entity-type":"item","numeric-id":4390607,"id":"Q4390607"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9eb431c2dcc59e79bc0eaeb4943d37d27cdc7730","datavalue":{"value":{"amount":"+0.96720105","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1322291$9E0DBC55-91DF-4ABC-8B5F-6AC7BE69C1BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"538746e0d3fce2ccf2fbf0fcaba95cde728fb5b8","datavalue":{"value":{"entity-type":"item","numeric-id":3998644,"id":"Q3998644"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"86f50a141955e5fa342cc63c7aba8cff422c3638","datavalue":{"value":{"amount":"+0.9533888","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1322291$3D5897D9-CF2F-4148-9017-B612B90E8F28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"800a06ee0ef1ccc2320ebaed3496794e151ffbcd","datavalue":{"value":{"entity-type":"item","numeric-id":5556306,"id":"Q5556306"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2f14c05882bb9364a6ee1b4989870c9131449da3","datavalue":{"value":{"amount":"+0.92805403","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1322291$E83217F2-9C89-448A-A765-24152A7E33CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2db1d821bd9d3b437dec3d97d20db75bfda14737","datavalue":{"value":{"entity-type":"item","numeric-id":4735214,"id":"Q4735214"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fe704e1dc71c306cbd5229dfdd5bcd961eaebdfb","datavalue":{"value":{"amount":"+0.928054","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1322291$6D061CC6-5338-464B-B368-9E37B29AB0D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ce294b8ccfb6b482c8afe402390e66d1b5adabd8","datavalue":{"value":{"entity-type":"item","numeric-id":5251981,"id":"Q5251981"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"55fe1f1d57f20a0834659600fce4382f0e152d65","datavalue":{"value":{"amount":"+0.9279775","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1322291$10D155E3-0423-4AF2-88BD-6CED73CA59A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f363e2a39c11010e52229a65b1f5589048071e64","datavalue":{"value":{"entity-type":"item","numeric-id":4852861,"id":"Q4852861"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"965b38d01e5595eafd5e6023f524f2acaea95613","datavalue":{"value":{"amount":"+0.9182847","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1322291$88DEDDBE-0DB4-4F6B-AE9C-3E901115A5D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"15bd38e954937f4dc6b451e48af299d5b3fb9d1e","datavalue":{"value":{"entity-type":"item","numeric-id":4254306,"id":"Q4254306"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"345bdc87fd2f3f81d5c765645713c6fa1e64c519","datavalue":{"value":{"amount":"+0.9172604","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1322291$F6FF6F34-B1D2-4232-97C4-B43B2F59F2D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8e2cc43df3ab485d3a1afb0eed4f1cc58369b7cb","datavalue":{"value":{"entity-type":"item","numeric-id":4876959,"id":"Q4876959"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6be8c36a7697e0996fd284e293b07648106566ef","datavalue":{"value":{"amount":"+0.91458106","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1322291$D64D6587-8F24-410D-B626-497A1CF82A4B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a5b839a4d3e97598026d94504557da1ebfb0b751","datavalue":{"value":{"entity-type":"item","numeric-id":3029040,"id":"Q3029040"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"05289cc6b15ca6e70e0d9154835aa8c93170bc40","datavalue":{"value":{"amount":"+0.90745604","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1322291$FC0E81EF-B1F4-44F9-AAE4-470E3557A97F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Graphical decompositions","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Graphical_decompositions"}}}}}