{"entities":{"Q6945271":{"pageid":21175206,"ns":120,"title":"Item:Q6945271","lastrevid":84094571,"modified":"2026-05-09T22:14:15Z","type":"item","id":"Q6945271","labels":{"en":{"language":"en","value":"Partition of graphs with maximum degree ratio"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 8077846"}},"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":"Q6945271$241C5689-E656-4EA1-8A2C-8A02FC448C23","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d709392a387c051ee64e5667db20f06ff81dd60a","datavalue":{"value":{"text":"Partition of graphs with maximum degree ratio","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q6945271$F0A67BF5-E660-45E6-A2A0-156D854C6A0F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"042e82dc0e60e57362109d070a373d8aab3e0735","datavalue":{"value":"1571.05233","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6945271$A304DBE4-0581-47DC-97BC-B0F7744D547F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"16d1e117879495f7d9281118bf00192afb436c70","datavalue":{"value":"10.1007/S10479-025-06615-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6945271$B5D0F8E5-16FE-46B1-8CE4-3FA4EA29AA65","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c2b1e02a6fcb887056202b8f0fcefd9042723161","datavalue":{"value":{"entity-type":"item","numeric-id":2208333,"id":"Q2208333"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6945271$F596CFB9-8842-4321-8159-B78AA39E2E5C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9509e521cab85798f9b2b4030f3d9d6300552f2e","datavalue":{"value":{"entity-type":"item","numeric-id":963416,"id":"Q963416"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6945271$9DAA18E9-8CAB-4DEF-A066-96868F6CEFE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8dc252585538d2ef4e07162cef61c79e437a3117","datavalue":{"value":{"entity-type":"item","numeric-id":411243,"id":"Q411243"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6945271$F675F57B-57A7-4B54-9136-EAF9BEC47D01","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"8f57d1123ebbbd10d621b3552a672e7729202712","datavalue":{"value":{"entity-type":"item","numeric-id":59875,"id":"Q59875"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6945271$6DCDC860-8146-407C-A75F-F67BCEE69929","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"29889ad190e820a4785d33bbfa34e41288b63a3a","datavalue":{"value":{"time":"+2025-08-09T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q6945271$41584489-5486-4115-BC20-DED95B6B31BF","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9772be543a45945e42d8fc35430fef0dd6be4c84","datavalue":{"value":"The authors in this work are concerned with the important problem of partitioning the vertex set of a graph subject to certain constraints. Their problem is related to the degree ratio. First, the authors define what they mean by the satisfaction number of a vertex $v$ in $V_i$. This parameter is defined as the ratio of the size of the closed neighborhood of a vertex $v$ in one of the two partitions $V_1$ and $V_2$, say $v$ is in $V_i$ to the size of the closed neighborhood of $v$ in the whole of $G$. The degree ratio is then defined as the ratio of the largest worst ratio over all nontrivial partitions. The worst ratio over all the vertices then reveals the quality of the partition. In this article, the authors compute this degree ratio parameter for certain classes of graphs. They also derive certain NP completeness results for the family of regular graphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q6945271$37432306-B9A1-430A-A698-CF4F2B9CE2CE","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c754ec9fae75fbeaa94e089f2452dc68e1235b5c","datavalue":{"value":{"entity-type":"item","numeric-id":198726,"id":"Q198726"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6945271$3531046E-7B6D-4BE7-BDD7-4D91A83371FE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d765cc4b218ae225bb23e4f50aa85c5b7550ef66","datavalue":{"value":"05C72","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6945271$7D261505-1BF9-4414-A25B-D3FA681B9964","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6945271$66187FEE-6AA7-4BC3-A5EE-FE3C3B2B8F03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6945271$9FC09F8C-DDAE-4BA1-86CC-20FB3AF9C212","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3b63f05e337cabf5a232afbc4e13c3a4a3e74f5b","datavalue":{"value":"8077846","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6945271$20B6A758-AB78-4D61-B00C-EAE22710E16C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c515f341d483f1d2a5bcf8ed1aaa124d8d49f585","datavalue":{"value":"vertex-partition","type":"string"},"datatype":"string"},"type":"statement","id":"Q6945271$B90B21DF-3A5E-49F6-8D68-08835CFDCAC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"836bea7c436ccce30511c5f8aa493a69b2e903d5","datavalue":{"value":"edge-cut","type":"string"},"datatype":"string"},"type":"statement","id":"Q6945271$72894A9F-C904-4DBE-BCB3-9C84A4BD1A9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9217cf5fdf9311e03b0d651a5eac92fd9c7100c2","datavalue":{"value":"regular graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q6945271$4C9D1333-F0E2-48E4-BA5B-19047D074046","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3187e84c5efaed03d0bd9515713a70084404d3ee","datavalue":{"value":"bipartite graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q6945271$ACB61C21-8275-40C6-B545-8AFB1BCB295C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7fab00b76e2380b91d927fa1f76061260b583a96","datavalue":{"value":"degree ratio","type":"string"},"datatype":"string"},"type":"statement","id":"Q6945271$8F666D86-717E-4D56-82B0-09080CFECC6B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q6945271$D2FAC4FA-F6E0-411C-A82F-BC2617571FA6","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":"Q6945271$9B44968E-D0D5-484D-9CA1-B70F1C6B060A","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"9759af6568db2190bc489d60d0b9408c7b3e556c","datavalue":{"value":{"entity-type":"item","numeric-id":2825476,"id":"Q2825476"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6945271$D3BDBFD5-F88C-4D2A-9E2B-DF8ECC0E5EEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"361038be4236f81923e3a9c8270e6a3cc619d7d7","datavalue":{"value":{"entity-type":"item","numeric-id":976309,"id":"Q976309"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6945271$E8B0BD09-3ADF-4678-AC98-58ACD122BABD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"559dbe579a3334aacf82df2fdcef598c181017c4","datavalue":{"value":{"entity-type":"item","numeric-id":5422499,"id":"Q5422499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6945271$D1C365F6-1662-4E9A-A370-7E4833B4F30B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2128fcc7dd131688ca80e86b9ccd3255436687ec","datavalue":{"value":{"entity-type":"item","numeric-id":3320412,"id":"Q3320412"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6945271$89F740BB-505E-45C6-8407-E5CBB7832319","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c116981e4989a9286cba4d97ea556685f011b0f6","datavalue":{"value":{"entity-type":"item","numeric-id":2032346,"id":"Q2032346"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6945271$EB1C777B-21AA-4935-B1D5-EB5F757C6E9D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e48a5fca158a67ee3b7231dc9b3fb3df9a1ce36c","datavalue":{"value":{"entity-type":"item","numeric-id":1800399,"id":"Q1800399"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6945271$EB2007A5-4B9D-4B67-95FF-F8B070B080CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"96c24df0acd582836f7cdc1f8ec419292eb9dd6a","datavalue":{"value":{"entity-type":"item","numeric-id":1400002,"id":"Q1400002"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6945271$9C5496D1-9A85-47D5-BFAE-D2DA05D174FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fde5c4f6fac9956fe48fb7767822de40244a31e5","datavalue":{"value":{"entity-type":"item","numeric-id":5379812,"id":"Q5379812"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6945271$185859D0-E5DB-4D7B-8DD3-B45E770AE79C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3be6615220d55e5c7881c23051dfa7f36f1647a8","datavalue":{"value":{"entity-type":"item","numeric-id":4949575,"id":"Q4949575"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6945271$D1ADCEB4-A0AA-4E5B-A637-1FD5A4BF30DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"72726adcefd20ecdeea80ec29373f23b2f0da4b5","datavalue":{"value":{"entity-type":"item","numeric-id":4715286,"id":"Q4715286"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6945271$E827EB81-7F27-47D0-96F9-581EDBA8AF5D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Partition of graphs with maximum degree ratio","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Partition_of_graphs_with_maximum_degree_ratio"}}}}}