{"entities":{"Q1386472":{"pageid":1397212,"ns":120,"title":"Item:Q1386472","lastrevid":68835366,"modified":"2026-04-13T02:23:32Z","type":"item","id":"Q1386472","labels":{"en":{"language":"en","value":"Covering regular graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1154631"}},"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":"Q1386472$976EE14A-A5E9-43B2-825A-655F1C8BA7DC","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"92c08663538653fae3167a319b89c18887d95b0c","datavalue":{"value":{"text":"Covering regular graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1386472$ACBDE83D-64E0-49B2-96B9-D014F03951B3","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4233c7d4c336b4a01032e0e328489ea872334313","datavalue":{"value":"0895.05049","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1386472$8B1AA41E-B988-41A3-BA88-79706B28E9DB","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9034d743abb2e8189da1fd67afac14b0cf3088f3","datavalue":{"value":{"entity-type":"item","numeric-id":175587,"id":"Q175587"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1386472$B5B6CD86-44E6-464B-8207-07CECD9AB84F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d176ad615a4e6a7168d3f60eb001c162327a80ae","datavalue":{"value":{"entity-type":"item","numeric-id":175510,"id":"Q175510"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1386472$89297A8B-C820-4F9A-AEDA-F3A35DC58394","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7eb375132d882d088e307505ca1beab02aba0720","datavalue":{"value":{"entity-type":"item","numeric-id":300478,"id":"Q300478"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1386472$44E27C14-8FCF-46FA-BCDD-D957B275E506","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":"Q1386472$86E1A3C4-7E92-4131-AF26-8788E4937668","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e2bcebd569bbfb5b8b0063ba2286496f2af92031","datavalue":{"value":{"time":"+1998-08-10T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1386472$CF3AF0F9-BFD7-446D-86C3-C7CDBAC02CC3","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d9c1d7535713d23dbf7dbe53b3d11bc5ca3815a1","datavalue":{"value":"https://semanticscholar.org/paper/539d53c1487858417d8106aa10456718387fef04","type":"string"},"datatype":"url"},"type":"statement","id":"Q1386472$84E7F55B-E9D7-4AE2-8978-65042F2407BB","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ff7c91b3319f4e6b0d39d1b1118ba4ad963a0b44","datavalue":{"value":"A covering projection from a graph \\(G\\) onto a graph \\(H\\) is a ``local isomorphism'': a mapping from the vertex set of \\(G\\) onto the vertex set of \\(H\\) such that, for every \\(v\\in V(G)\\), the neighborhood of \\(v\\) is mapped bijectively onto the neighborhood (in \\(H\\)) of the image of \\(v\\). The authors investigate two concepts that concern graph covers of regular graphs. The first one is called ``multicover'': they show that for any regular graph \\(H\\) there exists a graph \\(G\\) that allows many different covering projections onto \\(H\\). Secondly, they consider partial covers, which require only that \\(G\\) be a subgraph of a cover of \\(H\\). As an application of their results they show that there are infinitely many rigid regular graphs \\(H\\) for which the \\(H\\)-cover problem---deciding if a given graph \\(G\\) covers \\(H\\)---is NP-complete. This resolves an open problem related to the characterization of graphs \\(H\\) for which \\(H\\)-COVER is tractable.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1386472$9157CCDC-A13D-49B5-B41A-C4C1BCF3CB47","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1386472$6BD1727B-449B-471F-B7B0-FB8808A4B6B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1386472$84F7AD9F-463C-4699-974D-8C379EC33F36","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7c2d017045dfb7a3ebbdefb9c745e290a29722e7","datavalue":{"value":"1154631","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1386472$7820044E-07FD-4E39-8053-3D1407DF3AC5","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"873771111cd8363356a633557a7554738c0ef637","datavalue":{"value":"covering projection","type":"string"},"datatype":"string"},"type":"statement","id":"Q1386472$683EDB1D-BC9D-47DB-A301-DDD1FC3BC854","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"67a3cad6f34cb067e3fbd8190982ae3d672c5be5","datavalue":{"value":"local isomorphism","type":"string"},"datatype":"string"},"type":"statement","id":"Q1386472$D08A9B4C-C9E3-4E0A-A755-39E579EB19CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2dd63886a1fdafa33f8d351cdb5349869ba5f369","datavalue":{"value":"\\(H\\)-cover problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1386472$3C2BF644-6D17-4668-A936-108E776663AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f88544854e4c89952eaccb6e2f34fc84e9b81e85","datavalue":{"value":"multicover","type":"string"},"datatype":"string"},"type":"statement","id":"Q1386472$C21F0ED4-847D-4EF7-8BE8-D3D1194C6B13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"66e1a1213682950f63f65fd446a2b75328c1ae4a","datavalue":{"value":"partial cover","type":"string"},"datatype":"string"},"type":"statement","id":"Q1386472$1FFAF34C-F211-4D4F-9E79-CA5C5A9863C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q1386472$D22342F1-4AA6-4954-81F8-797F86C6D0CF","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"094d61d1ff99e208b2511ef0c6fc952ca4052a28","datavalue":{"value":{"entity-type":"item","numeric-id":230778,"id":"Q230778"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1386472$40AA22AB-62E9-4DE6-BAD1-456B9431776E","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":"Q1386472$E5291765-CC17-4E48-8889-17F02121B5C2","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b3e7810ad7cbe4dc32eafa677097685ddce828cf","datavalue":{"value":"W1985986630","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1386472$8BBFA623-C0DF-4D4B-BA18-6B729F2686B8","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"c8213a6dc1fa284bfdedde71b2fc35e745595f18","datavalue":{"value":{"entity-type":"item","numeric-id":4017175,"id":"Q4017175"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1386472$2C875FEB-EC8C-49A9-9629-4525E70E32F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1314d75bdb6e36b43bc5d0e3c017df566a8ab0bd","datavalue":{"value":{"entity-type":"item","numeric-id":1135865,"id":"Q1135865"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1386472$8D75346D-0662-4CEC-B656-1B0FB2F05CDE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"73065e1f99acfea60791aaa874a6b317e685fafe","datavalue":{"value":{"entity-type":"item","numeric-id":4770409,"id":"Q4770409"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1386472$DC405D34-F576-47EF-A7B3-6190BDB165E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7d72bad8355c5182d55cd5155c0cadd32f0a1669","datavalue":{"value":{"entity-type":"item","numeric-id":3666879,"id":"Q3666879"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1386472$5306ED71-3D24-44AE-A964-46D823942C52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8eebe99e883aa678130e247b99961cf48a53fb0e","datavalue":{"value":{"entity-type":"item","numeric-id":1317492,"id":"Q1317492"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1386472$CBCD824D-69C9-473F-B566-8787E40388C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5e65d73ae8ce50631a13a2e25599a048bc2eda73","datavalue":{"value":{"entity-type":"item","numeric-id":4158479,"id":"Q4158479"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1386472$72D0C7A2-93E6-4D15-9FFA-0F97C9CC885D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ade29bb9c5c58c1fc73fbff734d987495a982508","datavalue":{"value":{"entity-type":"item","numeric-id":3757929,"id":"Q3757929"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1386472$961D16D4-9A2F-4BA5-BDAA-AEA29CE1E028","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"170ecfd2b9b7e7a2924588737498fa44d8754dd2","datavalue":{"value":{"entity-type":"item","numeric-id":1246168,"id":"Q1246168"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1386472$798CD78A-E6DA-4477-AE74-B372943A57D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"92a8e95d00afe5d00265b1e0c81f55467d9e9732","datavalue":{"value":{"entity-type":"item","numeric-id":5666582,"id":"Q5666582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1386472$9E252989-8D9F-4F37-BA2F-CB15358D2CC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"60e403eb17c760bc3ad5273c76e4e4bae4d48119","datavalue":{"value":{"entity-type":"item","numeric-id":1185095,"id":"Q1185095"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1386472$86BDABFD-98E8-4628-84FC-8DD7706932AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fec165abc7ade014841f417bcba31a647c17e0c7","datavalue":{"value":{"entity-type":"item","numeric-id":1100215,"id":"Q1100215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1386472$6B608267-85F5-4C3B-AD66-C96BCB2A9B45","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"631200adace0f14c2f6d92fc47cb2d9f5d82cdbb","datavalue":{"value":{"entity-type":"item","numeric-id":3928241,"id":"Q3928241"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1386472$AD4496A1-3D76-4B64-8095-77804ABF7222","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9b3de5d933aac98ce001a35d32a88fd2111d286a","datavalue":{"value":{"entity-type":"item","numeric-id":4747513,"id":"Q4747513"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1386472$2DA7B6E3-B907-4E96-9F0B-AFE1EEF8C27B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fc8d0e8b5957bb46d6c54c5df5f602ad7968742e","datavalue":{"value":{"entity-type":"item","numeric-id":5534009,"id":"Q5534009"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1386472$87A53D6F-24FE-49C3-B257-229BBF67B597","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"537d8d5beae92530eee16b7ed630cd3aae33492a","datavalue":{"value":{"entity-type":"item","numeric-id":2549328,"id":"Q2549328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1386472$781865A5-A1E3-4C5E-96E2-801A930C70FA","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"87a2d340c4d17c0daff30bf56c78f1108485485a","datavalue":{"value":"10.1006/JCTB.1996.1743","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1386472$6E0669CD-4EC8-493B-9EE9-E4299DC55655","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d96fe016bb39bad2941bf96b14e339e07900a559","datavalue":{"value":{"entity-type":"item","numeric-id":4373685,"id":"Q4373685"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6eef59a425990ae1f9eced1e99184d39085a1705","datavalue":{"value":{"amount":"+0.8504364490509033","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":"Q1386472$F347FB1D-4AF1-4D60-870A-E544882AA043","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1d265648de526e2e789b69fc933120e1ab0c903b","datavalue":{"value":{"entity-type":"item","numeric-id":5167767,"id":"Q5167767"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"32c63a474a3cc53e7180dc328dfc11cd9fb92005","datavalue":{"value":{"amount":"+0.8375505208969116","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":"Q1386472$138AC8CC-F72C-4807-912F-0521AB6E2CF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f0ffb1b6fd60ed07da5213194bbbd908d6110b2b","datavalue":{"value":{"entity-type":"item","numeric-id":2922636,"id":"Q2922636"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"33763f28a341b0b592e002d5ca4cd31255272d0c","datavalue":{"value":{"amount":"+0.8319826722145081","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":"Q1386472$A8D8E38A-916D-477B-9816-EB953CA28EED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9bfd73b4399060e505b6569762bfa788e2c8099f","datavalue":{"value":{"entity-type":"item","numeric-id":897866,"id":"Q897866"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"51f3cf8ecff5c7bdccd41af9ec09d89668e5a933","datavalue":{"value":{"amount":"+0.8244476318359375","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":"Q1386472$CD8BE99F-061E-4B64-8FB1-6F33015CEFE3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e82209196789a7f3850abe2e724724ab757467b8","datavalue":{"value":{"entity-type":"item","numeric-id":4474120,"id":"Q4474120"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"602e5c77c7c214aeb8c89d30c84c3cac3e972fd7","datavalue":{"value":{"amount":"+0.809387743473053","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":"Q1386472$7CF8A7A0-E3CA-498D-AD92-0966CDC6A0A7","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Covering regular graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Covering_regular_graphs"}}}}}