{"entities":{"Q1260772":{"pageid":1271522,"ns":120,"title":"Item:Q1260772","lastrevid":67145412,"modified":"2026-04-12T15:36:06Z","type":"item","id":"Q1260772","labels":{"en":{"language":"en","value":"Greedy construction of nearly regular graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 370660"}},"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":"Q1260772$52E80EBF-7736-47C2-818C-7A13F628CF76","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e9e5b90f2d2a17b8f3cf0694cc589c733dbb1e94","datavalue":{"value":{"text":"Greedy construction of nearly regular graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1260772$C9C33D7B-43A3-463F-B5E8-A10037368CB7","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ca6a7edbac91e557456e82dd8f222e8dbca9f3ce","datavalue":{"value":"0787.05076","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1260772$272F36A7-A8FB-42DE-B694-2D0803304E10","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b113bc4ac7ed430093230b872c083cde59919509","datavalue":{"value":{"entity-type":"item","numeric-id":166287,"id":"Q166287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1260772$1E0D8ACB-60E1-4585-9C78-9204B5F7403D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"db72996963a9193f3c38ca9de20c1dcbfa0ae1ee","datavalue":{"value":{"time":"+1993-08-25T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1260772$E155DD5C-470E-451C-88EC-4E31BC88F589","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"eaba73cac648949f27150cf26d8fd9f06cc664f1","datavalue":{"value":"The authors study a sequence of nearly regular graphs which are built starting with the empty graph on \\(n\\) vertices and adding randomly one single edge at each step in such a way that at each step the new constructed edge must join some vertices with minimum degrees. The function \\(f(n,m)\\) is defined as the largest difference of degrees in such constructed graphs with \\(n\\) vertices and \\(m\\) edges. Main results:   Theorem 1. For any positive integer \\(d\\) there exist positive integers \\(n\\), \\(m\\) such that \\(f(n,m)\\geq d\\).   Theorem 2.  \\[ \\begin{alignedat}{4} &f(4k,&&\\;4k^ 2+9k-3)&&\\geq 3 \\qquad &&\\text{for }11\\leq k\\\\ & f(4k+1,&&\\;4k^ 2+10k)&&\\geq 3\\qquad &&\\text{for }9\\leq k\\\\ & f(4k+2,&&\\;4k^ 2+11k+3) &&\\geq 3\\qquad &&\\text{for }4\\leq k\\\\ & f(4k+3,&&\\;4k^ 2+14k+6) &&\\geq 3\\qquad &&\\text{for }10\\leq k\\end{alignedat} \\]  Theorem 3.  \\[ \\begin{alignedat}{3} &f(4k, &&\\;4k^ 2+9k-4) &&\\leq 2\\\\ &f(4k+1, &&\\;4k^ 2+10k-1) &&\\leq 2\\\\ & f(4k+2, &&\\;4k^ 2+11k+2) &&\\leq 2\\\\ & f(4k+3, &&\\;4k^ 2+14k+5) &&\\leq 2\\end{alignedat} \\]  The paper closes with some supplementary results and problems.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1260772$439CF4EB-152E-4CF1-AADA-0B7673A737D3","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"ebe4d44a08a58073803722e37fc039de15c45af0","datavalue":{"value":{"entity-type":"item","numeric-id":761465,"id":"Q761465"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1260772$F4653ABA-2DC5-4B93-938E-2EC0F734D541","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1260772$D38CF373-1BD3-4BB0-A632-AEC171FC738F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1260772$19ACE526-E0D8-413B-9716-381D433C7BD2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1260772$8CF52302-C6C9-4300-942D-D1A170E524E9","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4bd4a1856f31e5e7370b3a62551dea0350173bb1","datavalue":{"value":"370660","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1260772$A73DEA25-6407-48F2-A161-5E2491D5333A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bcc771f9c4cbb132a4fb9368403bb895cba44b70","datavalue":{"value":"matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q1260772$5A34F7A2-CA1F-4127-A633-64EFC93C81A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"534805fa6153b1b3786edcd60407ef0861005e9a","datavalue":{"value":"tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1260772$2DB3DDB2-D0B2-4AB7-A87D-64D43B091998","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5905a10d668a74111ed97fdc58213f68080b9194","datavalue":{"value":"factor","type":"string"},"datatype":"string"},"type":"statement","id":"Q1260772$2C8AEC3C-07DB-4E73-85DC-DD2418ABB5C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b999a30face15aad7449f079f4627b1e5e0eb2bc","datavalue":{"value":"coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1260772$23D5BA8E-CF3B-4174-8F80-8AC831F8C649","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ae3c5336f89a91dce30b6762e0fc085e6a33eef7","datavalue":{"value":"nearly regular graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1260772$DA4788F4-6027-4E52-A158-6B41D5F13846","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"69ea5b69d0be7e1d5aded4795bf1838bfcba2141","datavalue":{"value":"degrees","type":"string"},"datatype":"string"},"type":"statement","id":"Q1260772$F24CD323-85F5-402D-B22B-BFFDB6C0F0AE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"306d9099ef8452dabdd265171a602e1aa51bd912","datavalue":{"value":{"entity-type":"item","numeric-id":162994,"id":"Q162994"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1260772$B847DEF5-11AA-4991-8C9B-42491AC75E90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f1ce2eda4e7885252bd7e0f0de2009b4f5f5d880","datavalue":{"value":{"entity-type":"item","numeric-id":6481731,"id":"Q6481731"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1260772$AD6CEC52-7E64-4482-B87C-83566EE7C048","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":"Q1260772$D00DFFF7-81F3-4A66-BCC3-540B3DC7D9D3","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e8f959264ba12ce02840602d72499a322d2c350a","datavalue":{"value":"https://doi.org/10.1006/eujc.1993.1025","type":"string"},"datatype":"url"},"type":"statement","id":"Q1260772$BA2429ED-A20B-43E0-9AF4-D1C50AF46F93","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"8b72ebb2c3b7cb9a210e862153128d8c4af8f500","datavalue":{"value":"W2027013453","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1260772$A500FAAA-60A0-44C2-9E83-DFE66C482E7D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f706ca03ee435534cd6b64c4cc1dcd628ddf004c","datavalue":{"value":"10.1006/EUJC.1993.1025","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1260772$52188BA6-CDE0-4AA6-A0F5-3F9370661EDF","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"16b34cd7a32585db925b5c89134b13b60569268e","datavalue":{"value":{"entity-type":"item","numeric-id":6073632,"id":"Q6073632"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f4ed004dc00860582c870af240968c9ff05ccbb7","datavalue":{"value":{"amount":"+0.8911789","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1260772$7E433DAA-B552-4604-B585-9BFAC8A53183","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6c198bede4a4ba07edfe0d87487aa608e69e623e","datavalue":{"value":{"entity-type":"item","numeric-id":3104256,"id":"Q3104256"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"67333f5e46c10513649f75639d0246cc27ca4be5","datavalue":{"value":{"amount":"+0.87963176","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1260772$748CDD77-916E-4022-B5A8-EB79BCE1C706","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d5ff259608836e04b4e81af83dc9c73169a1b09e","datavalue":{"value":{"entity-type":"item","numeric-id":729791,"id":"Q729791"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4ff84463eab6788b4f43162f8673603c539d6817","datavalue":{"value":{"amount":"+0.8711666","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1260772$9078EB5D-2E20-42AE-A7A8-40EFF52006D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8fc13fa73548cf55355e5edb554bfb8a3c1e7ad7","datavalue":{"value":{"entity-type":"item","numeric-id":5521322,"id":"Q5521322"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2bffefa860963db801aaffaea671d7488544b4b4","datavalue":{"value":{"amount":"+0.8705781","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1260772$C89C21DF-588B-4029-9ABA-EDFDCE191DB0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"318b2d9fb375f1f8b26d501cc26bbe2f01449e25","datavalue":{"value":{"entity-type":"item","numeric-id":3150731,"id":"Q3150731"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"01d73b0f68ff2e186f98ec826e0863bd804d5ecf","datavalue":{"value":{"amount":"+0.8705284","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1260772$6361800F-0C1C-48C2-A835-087B6A04F4AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6f6a0e88f4f7dd045d2884023b6589f6a18fcfe6","datavalue":{"value":{"entity-type":"item","numeric-id":442380,"id":"Q442380"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"260dd5453267777de7c4953dd226cedce1dcb607","datavalue":{"value":{"amount":"+0.8672317","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1260772$FA3A69BA-116E-4379-AF62-7FCC50485244","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b6eee73951b7738f0b9988d1977b5ffecbe203e0","datavalue":{"value":{"entity-type":"item","numeric-id":4405787,"id":"Q4405787"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"251946c8d1e69a26adb75d301f71d3277a88b397","datavalue":{"value":{"amount":"+0.8662108","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1260772$B9CE38D3-F50A-4EC2-AD01-45058FA14A9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ff0d330f33f0575ebc7ad42f7ff7633c83dec514","datavalue":{"value":{"entity-type":"item","numeric-id":2712526,"id":"Q2712526"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"754990bdef79154b3760ad652b1a06c79fe644e9","datavalue":{"value":{"amount":"+0.8657323","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1260772$982BD169-1CD3-4122-8AD3-73B0CD44100A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c3acf662b40a44ffb25c2548c03b4bbf1c6bed9e","datavalue":{"value":{"entity-type":"item","numeric-id":5251988,"id":"Q5251988"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9a1a8619ea91182482260fdca7b91a7ebe972643","datavalue":{"value":{"amount":"+0.86573064","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1260772$5DF561D6-8BCD-4BB5-98D8-FA16BA8C061A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"50372cb65af2e5d3cd91ba157a10e8bb1b0ab096","datavalue":{"value":{"entity-type":"item","numeric-id":4229267,"id":"Q4229267"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"28f0fb21c1d424ee54bd0202bc9e0ea652e024cf","datavalue":{"value":{"amount":"+0.8639461","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1260772$D7F6FDA8-268E-482A-AFF7-4342173C18D4","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Greedy construction of nearly regular graphs","badges":[]}}}}}