{"entities":{"Q868330":{"pageid":870178,"ns":120,"title":"Item:Q868330","lastrevid":64958571,"modified":"2026-04-11T23:21:49Z","type":"item","id":"Q868330","labels":{"en":{"language":"en","value":"Reconstructing graphs from size and degree properties of their induced \\(k\\)-subgraphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5130425"}},"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":"Q868330$3C8A2A53-DBF7-4AE3-A95A-3226626ACFE7","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"fdebd4eec6c6821c403bef8f6352be61ea68b95b","datavalue":{"value":{"text":"Reconstructing graphs from size and degree properties of their induced \\(k\\)-subgraphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q868330$2885198B-6D42-43C8-81A7-CDBD2809EF59","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1fac8e0c7766d5a079bec344e905cf760dc8ef98","datavalue":{"value":"1119.05071","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q868330$4A13B71C-F4D2-44C7-91CD-DD879126CB2A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"4ed6f21f55f5293ad80f20217ff98c9b7054441c","datavalue":{"value":{"entity-type":"item","numeric-id":168472,"id":"Q168472"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868330$4CA7422E-566C-4314-A9E1-9FCB0D19D2AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6a76e14dae6cbb3abcd2d6da25c84b7ddc989b2f","datavalue":{"value":{"entity-type":"item","numeric-id":186196,"id":"Q186196"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868330$26F724EA-7CB8-4789-9A83-DD65E64E70B9","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":"Q868330$6A5AD983-A722-457F-8E89-657A6FE95FAA","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3af4457e51d097fa27d84537ba93ffccbacd245f","datavalue":{"value":{"time":"+2007-03-02T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q868330$874CA258-005A-4ECD-A498-45A72F0D6B24","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"53610dd5704c4af2e3d3045a3bcf2bea180d948d","datavalue":{"value":"The following variant of the graph reconstruction problem is considered: given the information that all induced subgraphs on \\(k\\) vertices of an unknown graph \\(G\\) on \\(n \\geq k\\) vertices satisfy a certain property, can we determine the graph \\(G\\)?   In this paper complete solutions are given for all possible values of \\(k\\) and \\(n\\) and the following properties:   \\((P_{a})\\) All induced \\(k\\)-subgraphs are regular (not necessarily of the same degree).   \\((P_{b})\\) All induced \\(k\\)-subgraphs are regular modulo \\(m\\) (not necessarily of the same residual degree).   \\((P_{c})\\) All induced \\(k\\)-subgraphs have one of two possible numbers of edges.  Complete solutions for every \\(k\\) and sufficiently large \\(n\\) are given for:  \\((P_{d})\\) All induced \\(k\\)-subgraphs are biregular.   \\((P_{e})\\) All induced \\(k\\)-subgraphs have a bounded difference between the maximum and the minimum degree.","type":"string"},"datatype":"string"},"type":"statement","id":"Q868330$EDB6268D-C4CF-47A7-9319-9B815E6B8E7B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2e742a171e2cc4a4f154f55124e2a34e0da3eb3e","datavalue":{"value":"05C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q868330$CF57615E-0AE5-4BFB-9591-231D3FEE7E94","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"edae6dbcb981699e322547c52b22c21860312673","datavalue":{"value":"5130425","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q868330$8FF943E0-33E7-433E-9514-5F42CAD28798","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"229adf8371e5ec4b765b87e45634a5fda957368e","datavalue":{"value":"graph reconstruction","type":"string"},"datatype":"string"},"type":"statement","id":"Q868330$B3AEC569-D31F-4BE5-B267-21384931BBCD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eb4dbee0d48d17c0702756f23f68f3af28651233","datavalue":{"value":"induced subgraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q868330$4149D7DA-2E3A-4F19-B83F-E207DC6D389C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9217cf5fdf9311e03b0d651a5eac92fd9c7100c2","datavalue":{"value":"regular graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q868330$9995E65B-3DA0-42CA-92CF-2276C06570E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"308cf63ea8c077f8633f0af8aef370fde0dd7b99","datavalue":{"value":"degree","type":"string"},"datatype":"string"},"type":"statement","id":"Q868330$3ACB48D7-AFCD-4B0F-85B2-64FE8E04873E","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"a45b400d22190ce8d9d8376830240adc5a55cd78","datavalue":{"value":{"entity-type":"item","numeric-id":367043,"id":"Q367043"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868330$9F7C4409-4B95-4B4F-80D3-7813211365B1","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":"Q868330$7EF72667-1ABF-4637-AF59-6F8C2E987604","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3ec1090bd1f29e7289be4cebfe68b0aa0d5768f2","datavalue":{"value":"https://doi.org/10.1016/j.disc.2006.06.031","type":"string"},"datatype":"url"},"type":"statement","id":"Q868330$940698C0-F115-4AB7-8BF2-F1430FAACE15","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"1f693c1d0194c7059fe33659839464dd8c09b7f6","datavalue":{"value":"W1978471807","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q868330$6CEEB5D5-0928-471D-B2BB-BAE2809F61AD","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"23c18af0ca63ae9d823049ed15f3ccd550ad23bc","datavalue":{"value":{"entity-type":"item","numeric-id":1344609,"id":"Q1344609"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868330$4B53B410-9E1F-4BBF-9CE2-12E92200BC25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"72bdc200c096a90cb093d01083b69c58672a0aa3","datavalue":{"value":{"entity-type":"item","numeric-id":3682518,"id":"Q3682518"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868330$E92EFB08-4791-4500-A878-E8D81D18D2EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ade61a9c825af534cbdcfe8e4b029b34b0c73be9","datavalue":{"value":{"entity-type":"item","numeric-id":3975132,"id":"Q3975132"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868330$F8C9943B-954A-46DC-92BB-071B361EA04A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"972f68f7936ac0c81f1d2f2f31bf6146ee04f9ec","datavalue":{"value":{"entity-type":"item","numeric-id":4697504,"id":"Q4697504"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868330$16E81C56-190F-4C91-BA43-9CD0ACD95B15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"34a72f75e2ed81fc276cd52c969ad2b34b36d462","datavalue":{"value":{"entity-type":"item","numeric-id":2713604,"id":"Q2713604"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868330$692564AD-DCE6-4F8B-A4ED-2858C9E97518","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"77b42f48331075127bde2eb83df948e64444796c","datavalue":{"value":{"entity-type":"item","numeric-id":1296525,"id":"Q1296525"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868330$FFAD6CA6-C058-4B25-B51E-5217085DA9D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1e5672cb2d248532c9e0e0c61ff6c5206f3e8f3c","datavalue":{"value":{"entity-type":"item","numeric-id":2760991,"id":"Q2760991"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868330$F715199C-B7EB-423A-B075-CD5701A144F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0023baf8e712128f0c9990ef3e30709574016c6c","datavalue":{"value":{"entity-type":"item","numeric-id":1301700,"id":"Q1301700"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868330$83B95E41-D9A3-4A86-B156-3E3FF7FD78EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"30243bfa38e252b8b75f04eef73ee19bba2bd15d","datavalue":{"value":{"entity-type":"item","numeric-id":769076,"id":"Q769076"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868330$B84E6B09-05DB-4E5A-B0B2-5DC95C2A6FAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"33fd8703b2a4334ea88d399c35fe6c9fd6064f7c","datavalue":{"value":{"entity-type":"item","numeric-id":3272973,"id":"Q3272973"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868330$E25E518A-22A8-45AC-9C01-4C70F1905F61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2ad2fe8dd86fee87642683d5794ea0cbe53231bb","datavalue":{"value":{"entity-type":"item","numeric-id":3259049,"id":"Q3259049"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q868330$5450ACD6-4BBC-4D1B-97D5-AA88CAF310D5","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"307d5057792fdbb21e32c543d622ba1d9ee791e9","datavalue":{"value":"10.1016/J.DISC.2006.06.031","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q868330$CCB55731-3C50-4666-AA94-18530346AA13","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f902e1728dea829db7a849cb9cc47ccb82aaec10","datavalue":{"value":{"entity-type":"item","numeric-id":3718756,"id":"Q3718756"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6be2ea2c2492524b8ea252f86c18c40ddc0b0af5","datavalue":{"value":{"amount":"+0.8178485631942749","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":"Q868330$76220B8B-70A4-4ADF-A96D-CBF7431684C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b228cbe15521729ad825730e9a2fa22d11b90941","datavalue":{"value":{"entity-type":"item","numeric-id":4632019,"id":"Q4632019"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2f8143738fd362de95c26f59bae5f9e9ebe44e53","datavalue":{"value":{"amount":"+0.8002129197120667","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":"Q868330$4CF6962C-0578-4685-9FCF-610AEFDF0881","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"44bb6586369a2dc804e5c6eb730a04a28cad2b4e","datavalue":{"value":{"entity-type":"item","numeric-id":908942,"id":"Q908942"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"77e0be793aaa772e2bb2e91d75b9a43f7be44348","datavalue":{"value":{"amount":"+0.7965295314788818","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":"Q868330$48A58BBB-7521-4BC0-AC61-2E1ACDEAB8B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fd868578e49a1df4998f4e4ab5008c0dce2f5488","datavalue":{"value":{"entity-type":"item","numeric-id":4879723,"id":"Q4879723"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"88112ad285151c9c6df18df2631cafbb07d1bbdc","datavalue":{"value":{"amount":"+0.7910858392715454","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":"Q868330$26030CC3-0809-4595-AE02-243F94B20E3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a3e96d604d83bf1e1d22802e5088ea9c90055130","datavalue":{"value":{"entity-type":"item","numeric-id":1772201,"id":"Q1772201"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a72c2ac71ebbde8ec7e168eb71202b4a36b03f4e","datavalue":{"value":{"amount":"+0.7839558124542236","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":"Q868330$F52B140D-46FD-4551-9FC4-4860C7CCAE85","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Reconstructing graphs from size and degree properties of their induced \\(k\\)-subgraphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Reconstructing_graphs_from_size_and_degree_properties_of_their_induced_%5C(k%5C)-subgraphs"}}}}}