{"entities":{"Q2519016":{"pageid":2529759,"ns":120,"title":"Item:Q2519016","lastrevid":57960039,"modified":"2026-04-03T06:12:11Z","type":"item","id":"Q2519016","labels":{"en":{"language":"en","value":"Hypomorphy of graphs up to complementation"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5495802"}},"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":"Q2519016$8C452640-195C-4DE6-B6BB-3B41AEF757D3","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ef149a8064918546f4c01a14ee18b3f7a6e628cc","datavalue":{"value":{"text":"Hypomorphy of graphs up to complementation","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2519016$3DE74F99-E98C-47C5-AA47-6FDEB25A7A2A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"022bc6f0a24a6472cb623980934aa9cc3ead96c3","datavalue":{"value":"1175.05095","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2519016$AEE8DE58-448B-4A91-9F2C-5DAB00238631","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f5fa2340b303d9935625fdf525c1aaf08078308d","datavalue":{"value":{"entity-type":"item","numeric-id":404398,"id":"Q404398"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2519016$08AB15C4-0E38-4399-9F34-5A46773EED0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"fcf1e8a796181b6c2c11ed91d7cca7830161df08","datavalue":{"value":{"entity-type":"item","numeric-id":343742,"id":"Q343742"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2519016$D83BEAE9-6FC6-4DBD-85B8-A3A9507C168B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"65e0030acd98cbe4786cbae362aba391b5681a10","datavalue":{"value":{"entity-type":"item","numeric-id":186055,"id":"Q186055"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2519016$93E2D1E4-9ED2-40E8-9EDC-A5BAC7405CCA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f432d530e490265454dcc2cd922b1999995622bc","datavalue":{"value":{"entity-type":"item","numeric-id":286754,"id":"Q286754"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2519016$37985FD6-4482-40F6-B60A-76B995E42DA0","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f07f6fd6d97bd24ff86249abf8a501d3b63b437d","datavalue":{"value":{"entity-type":"item","numeric-id":256978,"id":"Q256978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2519016$036B7780-8319-4C93-B784-4DD07A2601D5","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ecf289ffa08c547e658749b84476576936008772","datavalue":{"value":{"time":"+2009-01-21T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2519016$9CFF0146-C826-4D9A-8FCB-F344CECFC6DF","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3060300587f0f49edc8c88987efa461da164c775","datavalue":{"value":"https://arxiv.org/abs/math/0601118","type":"string"},"datatype":"url"},"type":"statement","id":"Q2519016$8176749C-3D16-4892-9DC0-850D62E95BFD","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c45c1691eb005551d3749bb98dc01c12641c877b","datavalue":{"value":"For any graph \\(G\\) and \\(K\\subseteq V(G)\\) let \\(G[K]\\) denote the subgraph of \\(G\\) induced by \\(K\\). It is well-known that if two graphs \\(G\\) and \\(G'\\) on the same set of \\(n\\) vertices are such that \\(G[K]\\simeq G'[K]\\) for all subsets \\(K\\) of vertices of size \\(k\\), for some \\(2\\leq k\\leq n-2\\), then \\(G\\) and \\(G'\\) are identical. In this paper the authors look for similar results if the condition on \\(G[K]\\) and \\(G'[K]\\) are relaxed in this fashion. Two graphs on the same set of vertex are said to be isomorphic (equal) up to complementation if \\(G\\) is isomorphic (equal) to \\(G\\) or its complement \\(\\overline{G}\\). They are called \\(k\\)-hypomorphic up to complementation if, for every \\(k\\)-element subset \\(K\\) of \\(V\\), the subgraphs \\(G[K]\\) and \\(G'[K]\\) are isomorphic up to complementation. A graph \\(G\\) is said to be \\(k\\)-reconstructible up to complementation if every graph \\(G'\\) which is \\(k\\)-hypomorphic to \\(G\\) up to complementation is isomorphic to \\(G\\) up to complementation.  The authors give a partial characterization of the set \\(\\mathcal S\\) of ordered pairs \\((n,k)\\) such that two graphs on the same set of \\(n\\) vertices are equal up to complementation when they are \\(k\\)-hypomorphic up to complementation. In particular they prove that \\(\\mathcal S\\) contains all ordered pairs \\((n,k)\\) such that \\(4 \\leq k \\leq v-4\\) and that \\(4\\) is the least integer \\(k\\) such that every graph \\(G\\) having a large number of vertices is \\(k\\)-reconstructible up to complementation.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2519016$1FFBDF2D-8C6D-455E-8EA7-A6F5EBBE8B87","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"3b6fe1f213720dd616a466b95779de3e7abac963","datavalue":{"value":{"entity-type":"item","numeric-id":394315,"id":"Q394315"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2519016$619CA3C2-20D1-4F75-93CA-D314BB530D3C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2e742a171e2cc4a4f154f55124e2a34e0da3eb3e","datavalue":{"value":"05C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2519016$6129221D-B0DA-4DFB-9F0B-5A6B659342C4","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2947f97aed774e23c4071ec77436115f5744006b","datavalue":{"value":"5495802","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2519016$77E5FD24-8DB9-4081-B6F2-1E7BA4017572","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ddc14051a93e8c78a1da682d6f4184d91e9c6088","datavalue":{"value":"graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2519016$44308E0A-9C8B-4DA4-A1C2-A86EB9207944","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"20cb5f900346d6218be2e7d1c87b3ca77a3b494d","datavalue":{"value":"reconstruction","type":"string"},"datatype":"string"},"type":"statement","id":"Q2519016$EA8898CD-E98A-4754-92DE-9089DC4587D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0cf57e3a578e4afe2bfefd6c41d9efe700a322d6","datavalue":{"value":"k-reconstruction up to complementation","type":"string"},"datatype":"string"},"type":"statement","id":"Q2519016$5025C2CE-6AC4-4813-B027-048611DD6864","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":"Q2519016$AE9CCA5C-73D5-40DE-AFC4-7197F5C5AEC0","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"49bebf6929d8e8eb3f4078919a66611475f19fc3","datavalue":{"value":"W1995540723","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2519016$5142FB90-3A6B-495D-93AF-0FE451866562","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"31e0fecf37e8bbc869084699ebc361b1e96d6394","datavalue":{"value":{"entity-type":"item","numeric-id":4871748,"id":"Q4871748"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2519016$B9D32BA3-053B-4C90-9BAC-F341E95CADEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e3c6fbe8e12c1d735bd0788ca535488d6d42896b","datavalue":{"value":{"entity-type":"item","numeric-id":4154892,"id":"Q4154892"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2519016$876333FB-371A-4341-AF3F-6ECB421CCA8E","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":"Q2519016$DAAA6CE9-C505-41C9-AFF0-F05F6CAB0F0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"225116f3b98655e4cbb084142670e8088acd17fd","datavalue":{"value":{"entity-type":"item","numeric-id":1076017,"id":"Q1076017"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2519016$013C55EB-8436-4ABB-8701-06A2960FA85B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1e9b19b2bec5333f4867d91c200cfb399261ca47","datavalue":{"value":{"entity-type":"item","numeric-id":5522934,"id":"Q5522934"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2519016$184D1315-51D4-4C87-ACE4-6366EA1DC4CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"64446cfa07d0da05af8d9a115a7e3f5d556175a2","datavalue":{"value":{"entity-type":"item","numeric-id":3142912,"id":"Q3142912"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2519016$0A24A510-2C6F-4EA6-B1C2-11ACBF055268","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"35f83a7a2b0d17687f81ce9b6ab2b7dfb43b11b1","datavalue":{"value":{"entity-type":"item","numeric-id":2549876,"id":"Q2549876"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2519016$72DC4766-C5D1-4CDE-9C5C-C6A5ADB42AB6","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":"Q2519016$9AC28ADF-5544-4F24-86D6-62D9D87AC13A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"797aac0e5a6a0e865b0b412cb42bbe3f1e9d7cce","datavalue":{"value":{"entity-type":"item","numeric-id":4265925,"id":"Q4265925"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2519016$690E4BF8-221B-4732-BE69-B95277BF187E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fe1d8d079de5ae1716c48ef2e3014b4b081e1de3","datavalue":{"value":{"entity-type":"item","numeric-id":1226161,"id":"Q1226161"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2519016$883B5F85-3B18-4B6A-9F57-7B0E13753C6B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"da72f670cd15a912328cc8970f72e50ad2428391","datavalue":{"value":{"entity-type":"item","numeric-id":5501213,"id":"Q5501213"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2519016$03B455C4-25D9-486E-A8CE-7110E68ABB40","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4586b57703cb244b4b02b29e80b33792d39cae7a","datavalue":{"value":{"entity-type":"item","numeric-id":2266719,"id":"Q2266719"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2519016$508EDB64-77CF-4957-ADB5-448CC5BB301B","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":"Q2519016$718EC0E9-BD9C-4309-85EC-C1032784E12D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ed790b782026ca0af1f2f2c8daa26146bb247bd0","datavalue":{"value":{"entity-type":"item","numeric-id":4002255,"id":"Q4002255"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2519016$49EA02B3-D16C-46AC-8F98-491AB8789010","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"93ef8bc849c5132d2a91c861867b4239e0e6597e","datavalue":{"value":{"entity-type":"item","numeric-id":1814091,"id":"Q1814091"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2519016$DF69C541-C2BB-415E-B9CA-5D4A83E7A040","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2fdbee26f75268aaf1343df0b14fccb69b1bbc80","datavalue":{"value":"10.1016/J.JCTB.2008.04.004","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2519016$FBF4DEA6-DCD0-48B7-9C39-B610512E83AA","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0304267e97936f7b4d9fec191124bb5e5c659e3a","datavalue":{"value":{"entity-type":"item","numeric-id":2861359,"id":"Q2861359"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2c84bbf1b90b1c763a21f3183b08b39191c02ee3","datavalue":{"value":{"amount":"+0.9272635579109192","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":"Q2519016$5789BE9F-27A4-4726-B509-295B01EF7205","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7e4a91ecef9f02f3326eabf77ee1c607ca504e0b","datavalue":{"value":{"entity-type":"item","numeric-id":1077435,"id":"Q1077435"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ac771143f5ba3fb59f4359448d34dbe11648ed96","datavalue":{"value":{"amount":"+0.818040668964386","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":"Q2519016$459EE577-DEE7-414E-9165-4AC806184FF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ef37feccadded0444d055adae721bfa93db0385a","datavalue":{"value":{"entity-type":"item","numeric-id":286755,"id":"Q286755"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b9c5e30b2711b772a39b4ab108eeec76b310dc3a","datavalue":{"value":{"amount":"+0.8148432374000549","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":"Q2519016$C56D5ED1-B5A8-4E94-AD01-AD27DBA6A524","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f214292875a115677e43d71d81d655714ccb1245","datavalue":{"value":{"entity-type":"item","numeric-id":1713868,"id":"Q1713868"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"495fb117dabd7f6254dd50da1d134fa428000612","datavalue":{"value":{"amount":"+0.813880205154419","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":"Q2519016$5C50F082-37B7-4AD8-94CA-C91DF810D005","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d21d5bdee4694626309291ffdc6298a1c8e42053","datavalue":{"value":{"entity-type":"item","numeric-id":1343810,"id":"Q1343810"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"067f98d81a4e061b939a5f3800e26171535dba82","datavalue":{"value":{"amount":"+0.8069657683372498","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":"Q2519016$41CB15FB-9BA8-46EB-9410-B0304BA6F668","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2519016","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2519016"}}}}}