{"entities":{"Q6864301":{"pageid":20682421,"ns":120,"title":"Item:Q6864301","lastrevid":84244595,"modified":"2026-05-14T03:25:11Z","type":"item","id":"Q6864301","labels":{"en":{"language":"en","value":"Minimum degree conditions for graph rigidity"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 8154525"}},"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":"Q6864301$F3B851A1-C4BC-4A48-8519-8DC95D8D7A2A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d558bfd5ac47ee0ffac53457ca7690ffcd691b17","datavalue":{"value":{"text":"Minimum degree conditions for graph rigidity","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q6864301$8F41CC46-B717-4A31-B6E9-5B339C18F3A6","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"dfcdf3253b97248e1738fdcf8a96e60bce795a4e","datavalue":{"value":"10.1112/BLMS.70279","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6864301$1A336D12-80D6-4DA1-9515-8F9C35660536","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b1cf400bc99a406c4d5dfcfdd4d04f10c4dc1f7f","datavalue":{"value":{"entity-type":"item","numeric-id":178700,"id":"Q178700"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6864301$D9C334D4-92EC-4722-8101-925366E605C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c52ca5185439cd888638e32e4e18fa057b09a98b","datavalue":{"value":{"entity-type":"item","numeric-id":2010624,"id":"Q2010624"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6864301$C748E161-B4BA-4F74-9A3F-C764A88B4334","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9ab89f2f36983fb428a0dbb6bbb0b4424ac4a7ab","datavalue":{"value":{"entity-type":"item","numeric-id":510342,"id":"Q510342"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6864301$9E95C4A6-7A5F-4ECC-91CD-04EC9112AF6D","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"01b7f37608d9f87bfa2998bb736dc8e29f05f57a","datavalue":{"value":{"entity-type":"item","numeric-id":2759195,"id":"Q2759195"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6864301$F70170DE-C309-4067-A2DC-8F756C6AE78F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5eb7c5cda49e010c65abc7807dc1347de80276b0","datavalue":{"value":{"time":"+2026-02-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q6864301$F2BF9E74-3FAE-4876-82B6-FD416660CA84","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"293432156b730e90325fc3af109ceafc0814c98e","datavalue":{"value":"This paper is concerned with the rigidity of \\(d\\)-dimensional frameworks. It seeks to give a lower bound on the minimum degree of a graph which would guarantee that any generic embedding of the graph into \\(\\mathbb{R}^d\\) is rigid. In this case, such graphs are called \\(d\\)-rigid.\\N\\NIt is well-known that if a graph is \\(d\\)-rigid, then it must be \\(d\\)-connected as well. On the other hand, if the minimum degree of an \\(n\\)-vertex graph satisfies the following inequality, \\(\\delta(G)\\ge \\frac{n+d}{2}-1\\), then it is surely \\(d\\)-connected. From the rigidity matrix, it is also known that any \\(d\\)-rigid graph must satisfy the inequality \\(|E|\\ge dn-\\binom{d+1}{2}\\), which is fulfilled if \\(\\delta(G)\\ge 2d-\\frac{d(d+1)}{n}\\). These observations led to the following conjecture of this paper.\\N\\NConjecture. Let \\(n>d\\ge 1\\). If \\(G\\) is an \\(n\\)-vertex graph with \\(\\delta(G)\\ge \\max \\left \\{ \\frac{n+d}{2}-1, 2d-\\frac{d(d+1)}{n} \\right \\}\\), then \\(G\\) is \\(d\\)-rigid.\\N\\NThis conjecture generalizes and is analogous to some earlier conjectures (see Conjecture 1.16 in [\\textit{M. Krivelevich} et al., J. Comb. Theory, Ser. B 175, 126--170 (2025; Zbl 1572.05230)] and Conjecture 38 in [\\textit{B. Jackson} et al., J. Comb. Theory, Ser. B 121, 432--462 (2016; Zbl 1354.15018)]) and in this paper the authors make advance towards this conjecture by proving it for small \\(d\\) values (Theorem 1.1), namely for \\(d\\le \\frac{\\sqrt{8n-15}-1}{4}\\) relying on a recent result of \\textit{S. Vill\u00e1nyi} [J. Comb. Theory, Ser. B 173, 1--13 (2025; Zbl 1564.05067)].\\N\\NThey also prove a result (Theorem 1.2) for larger \\(d\\) values, which is optimal up to a factor of \\(2\\). They divide their argument into two parts: whether \\(G\\) is close to being bipartite or not. In the second case, they use the Regularity Lemma, too. As a corollary of this second theorem, they obtain a new result (Theorem 1.3) regarding the pseudoachromatic number of a graph with given minimum degree, which might be of independent interest.\\N\\NThe authors also include an important note that points out that independently of them \\textit{T. Jord\u00e1n} et al. [``Degree sum conditions for graph rigidity'', Preprint, \\url{arXiv:2510.25689}] further improved their main results. Namely, their conjecture holds for \\(d\\le \\frac{n}{29}\\), and they also extended their second result (Theorem 1.2) to all \\(d\\) values.","type":"string"},"datatype":"string"},"type":"statement","id":"Q6864301$E358F8ED-341A-4876-863B-938FB93BD56D","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"acf5ec80e5ed98459e8bca1a46a6311cfbe445f8","datavalue":{"value":{"entity-type":"item","numeric-id":482227,"id":"Q482227"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6864301$5E3B8BAA-EA41-46FE-BDB8-F107F1810E33","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6864301$B54296A4-FEA6-489E-BF95-4BEFFF3E97C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2e16dba0a5579ad33b96782b068be975af060289","datavalue":{"value":"52C25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6864301$380EBECD-1EFC-4132-AC03-E80540E0E2BF","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a1806dd389569505156ea5ddb1215498460017c5","datavalue":{"value":"8154525","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6864301$8804AF10-3C2E-4752-BE98-40C8B50899C8","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"59b554e271d7ec77da22709df37d6bc801abf2bd","datavalue":{"value":"graph rigidity","type":"string"},"datatype":"string"},"type":"statement","id":"Q6864301$D584BD14-2250-40A4-A9CD-0FF1AF847CAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e5f8299477cf79d3a203e2a0b3972b2a7cc968fe","datavalue":{"value":"\\(d\\)-dimensional framework","type":"string"},"datatype":"string"},"type":"statement","id":"Q6864301$B9C36CD9-EBC9-4D0D-838C-EBEF89D72D81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c526bdff2982a5ef03771743a9f603652f41f79b","datavalue":{"value":"\\(d\\)-connected graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q6864301$72FACCFD-D662-4234-9F3F-E586AE154EFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6f9a7c80724e94f3fd7755f179a26487392c1530","datavalue":{"value":"generic embedding","type":"string"},"datatype":"string"},"type":"statement","id":"Q6864301$D3BCA0A4-6CB1-4587-9019-BF5888CB9E2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0fae8dc69695ed62681f89d7d9eea2d8a16b8684","datavalue":{"value":"minimum degree","type":"string"},"datatype":"string"},"type":"statement","id":"Q6864301$E55205EF-9076-4CAF-8B55-5EA525D0C451","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8cb27430d7b32d21b51f5888c9b0f62d80b403e4","datavalue":{"value":"Regularity Lemma","type":"string"},"datatype":"string"},"type":"statement","id":"Q6864301$CAB96DFB-9D51-4C9B-8EAC-FD133F3A2939","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":"Q6864301$C6B99B60-C6DB-4112-A691-58CBA2405632","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f8d9d7da8915b9a38383a508d9f03a1f60c908b5","datavalue":{"value":{"entity-type":"item","numeric-id":4173376,"id":"Q4173376"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6864301$C6AF2DF0-25D9-4068-B9F6-78442620C60A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bbe4c03c423b5987dea498fb446f21d97798246c","datavalue":{"value":{"entity-type":"item","numeric-id":1150631,"id":"Q1150631"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6864301$32C86BB2-6A93-44C6-803D-042C865C4DCE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c9667703d036775e594019e0945c5e9c26b491ab","datavalue":{"value":{"entity-type":"item","numeric-id":2701001,"id":"Q2701001"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6864301$4BA20567-00CB-47B1-9B78-B77FFD178FDD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6da70f99fd4cf6ae4ab94d8010048be644fea36c","datavalue":{"value":{"entity-type":"item","numeric-id":5567712,"id":"Q5567712"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6864301$581DFCB3-A592-46B9-B697-D28510495900","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"93cbb227dda8cc2e670b968c0716e9a74823b4e3","datavalue":{"value":{"entity-type":"item","numeric-id":3154668,"id":"Q3154668"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6864301$48030F8F-3BC9-48FB-A643-FAD06721B48D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"290744f1c55f1ea7f7653fc006e782d18a066547","datavalue":{"value":{"entity-type":"item","numeric-id":490983,"id":"Q490983"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6864301$2329CB01-EBB0-4E6A-858C-D203B265AF5C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3e30b1f121ec8054642dc24f98683e5ef7ee06ff","datavalue":{"value":{"entity-type":"item","numeric-id":4076414,"id":"Q4076414"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6864301$76E1B9B9-C1D7-40A5-8698-0D864581CF40","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ffd3bc7a2da26b1a8f6e371186d08420752388f6","datavalue":{"value":{"entity-type":"item","numeric-id":4279195,"id":"Q4279195"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6864301$D7F1FFE1-6C7B-4ED6-B68D-31F788D76D66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b278723c6c210db51043687d7d48805d32026b91","datavalue":{"value":{"entity-type":"item","numeric-id":5611635,"id":"Q5611635"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6864301$4EDF15FE-2A86-4F23-AC2A-B157F0AE9D41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2b6869714debbb8dc700f3e40a93a3aafea88191","datavalue":{"value":{"entity-type":"item","numeric-id":949754,"id":"Q949754"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6864301$1D8696BF-99E4-495C-8A81-81843459B589","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"186a668fd74ab9fd7d4beaf64d7782311c5c5861","datavalue":{"value":{"entity-type":"item","numeric-id":5246084,"id":"Q5246084"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6864301$7C3E7BDA-FE4B-4B4D-BA1B-96E41B23CC84","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1db71c2d6e8c00ae1d25e02265065be52938997d","datavalue":{"value":{"entity-type":"item","numeric-id":326825,"id":"Q326825"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6864301$EF8590A7-A48A-4199-9308-A87063EC7C16","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"28588578bb09af0b4bf0a3281ab6c8d321eb619b","datavalue":{"value":{"entity-type":"item","numeric-id":4519896,"id":"Q4519896"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6864301$00E34776-3288-44B2-B4BD-E2D65F15DBAD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3177f4263295de7eaceea3370c582254a5c6e4c7","datavalue":{"value":{"entity-type":"item","numeric-id":2990097,"id":"Q2990097"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6864301$849CB626-D5B9-4614-BDEB-4379A7953EAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5ed0b82ae82773b964a96367bdde8d8d4e478307","datavalue":{"value":{"entity-type":"item","numeric-id":4878666,"id":"Q4878666"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6864301$D6F50DF4-E4B9-4A68-96B6-33A5867627A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2612faf0a43c0aefb5740277cd6c0a06dbbfa558","datavalue":{"value":{"entity-type":"item","numeric-id":3333070,"id":"Q3333070"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6864301$8FDCCF89-A757-4D9A-85F3-CAC25C2A04D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"915f291c4713f741cd8146bfdcfebfc5dd913b3f","datavalue":{"value":{"entity-type":"item","numeric-id":6930172,"id":"Q6930172"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6864301$7ED5130B-8B2F-4E00-AF4D-E36C51E02932","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ef64f7847969d91ac58602e9acf9836f47122aad","datavalue":{"value":{"entity-type":"item","numeric-id":6135068,"id":"Q6135068"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6864301$2350C5A9-A180-4544-A94A-AB1AECAFDA4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c2e79977424fa87980b1a34befaece5ffa4e3029","datavalue":{"value":{"entity-type":"item","numeric-id":3837775,"id":"Q3837775"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6864301$7A66011D-80D3-4025-98F1-221903CB790E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"591071dcb52f7c1fd326ec11b658cfc146751665","datavalue":{"value":{"entity-type":"item","numeric-id":3694165,"id":"Q3694165"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6864301$E62E5A4C-490B-44D0-B611-0650B920A74A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ed2c50aeb446b65b736ecf15733f4ff471bdc815","datavalue":{"value":{"entity-type":"item","numeric-id":1850528,"id":"Q1850528"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6864301$CD0CAEC2-9A83-4D2C-8376-7BA096D5ED09","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d895315565a07909597eca69ff771607915e77e2","datavalue":{"value":{"entity-type":"item","numeric-id":6987048,"id":"Q6987048"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6864301$98C3F1FE-58CC-4FFA-AD51-DF6C434A5AB1","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Minimum degree conditions for graph rigidity","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Minimum_degree_conditions_for_graph_rigidity"}}}}}