{"entities":{"Q1753015":{"pageid":1763757,"ns":120,"title":"Item:Q1753015","lastrevid":72896136,"modified":"2026-04-14T08:36:37Z","type":"item","id":"Q1753015","labels":{"en":{"language":"en","value":"On the minimum size of an identifying code over all orientations of a graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6873093"}},"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":"Q1753015$C3807826-BB25-4610-A2D9-E3EA6560F871","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"cab0d997e077b5b8f6e765e3c6a6ac7a6dc941f9","datavalue":{"value":{"text":"On the minimum size of an identifying code over all orientations of a graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1753015$765BD18F-37D7-441F-91F6-A22CA22DA800","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a36f00a34dbc2b97c255c9d490893b1a6fd2ec34","datavalue":{"value":"1392.05105","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1753015$BF32B969-D587-4837-8A1D-D1E9FAF1C962","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6569876696c629cf07102d7345eae13f6693b19d","datavalue":{"value":{"entity-type":"item","numeric-id":484320,"id":"Q484320"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753015$EA58AE90-955D-4647-AF23-81962460314F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e4e8471076b9574779be9b69bcf04a02e8ebd18d","datavalue":{"value":{"entity-type":"item","numeric-id":186133,"id":"Q186133"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753015$CF49CE35-9F4F-4676-A1A7-ED7F361462E4","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753015$5E5D46A3-5364-4982-B1C5-86A006397D8D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"889be0f8e7c5593fd9d724762872dd9608a4e49c","datavalue":{"value":{"time":"+2018-05-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":"Q1753015$86426937-B92B-44EC-AA04-7607E5BE0F86","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"576b274cd3d20efa4812feaa2265bc296ec59d48","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i1p49","type":"string"},"datatype":"url"},"type":"statement","id":"Q1753015$10CD4D93-909F-41A2-BA83-96A38E49801A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0cafdbb416b4468eb35ef6005ee47c97a3b3b39d","datavalue":{"value":"Summary: If \\(G\\) be a graph or a digraph, let \\(\\mathrm{id}(G)\\) be the minimum size of an identifying code of \\(G\\) if one exists, and \\(\\mathrm{id}(G)=+\\infty\\) otherwise. For a graph \\(G\\), let \\(\\mathrm{idor}(G)\\) be the minimum of \\(\\mathrm{id}(D)\\) overall orientations \\(D\\) of \\(G\\). We give some lower and upper bounds on \\(\\mathrm{idor}(G)\\). In particular, we show that \\(\\mathrm{idor}(G)\\leqslant \\frac{3}{2} \\mathrm{id}(G)\\) for every graph \\(G\\). We also show that computing \\(\\mathrm{idor}(G)\\) is NP-hard, while deciding whether \\(\\mathrm{idor}(G)\\leqslant |V(G)|-k\\) is polynomial-time solvable for every fixed integer \\(k\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1753015$3799887F-8E01-46F0-911A-3FBBE86E2789","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1753015$12AD8F18-3AD2-4271-B899-C7F1E5A79A0B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1753015$090BB341-D326-42ED-BF6D-740A393ABC81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1753015$39266C78-D6A4-458D-8301-4F9C40ED9F64","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a49ab9533077041df6b4035aa32163879065ca26","datavalue":{"value":"6873093","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1753015$7011E6C3-98A6-4C1C-AB12-5BDEC726FCC7","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b00f74e58fd99cc80547758f2fae147dec06c299","datavalue":{"value":"identifying codes","type":"string"},"datatype":"string"},"type":"statement","id":"Q1753015$95EFA67D-9CD8-45A3-8DDA-6F3FCCEBBACE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"458f12def83c1367a32fd7e7e1dd4b0d57985296","datavalue":{"value":"orientation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1753015$F4C5C6A9-0D59-468A-B084-B83326DFAFEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba0cc3f7aaac8445724ef309c9eecb57f5a563d","datavalue":{"value":"computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1753015$C0DAFC73-3A36-4946-9B14-DF9722BAB966","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":"Q1753015$2611CCA4-8FC5-459F-8371-EEDCAFE7F80C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"8048e56e096fe00d3a631bc2da008d31b2daafa2","datavalue":{"value":{"entity-type":"item","numeric-id":5442540,"id":"Q5442540"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753015$77728A5F-3B2C-4270-A83E-641AED33E93E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b63a9982da0f189c1cd6053e45de12af16968df3","datavalue":{"value":{"entity-type":"item","numeric-id":2830060,"id":"Q2830060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753015$E96AB75E-5FF7-462D-A621-2C15A019E287","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8c006614db6bcec89cfe270202145ca2c2c794aa","datavalue":{"value":{"entity-type":"item","numeric-id":2495905,"id":"Q2495905"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753015$4BC4BCF6-BE7F-42F6-A3F9-AC0542E0FF54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e9b1fc02de44e20979e6d41cc974fe89c61b7402","datavalue":{"value":{"entity-type":"item","numeric-id":4677540,"id":"Q4677540"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753015$506E5B2C-4A8B-4284-BCE7-23E6A67439D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"32b89205996d95c14b68f126363352da45006567","datavalue":{"value":{"entity-type":"item","numeric-id":1401220,"id":"Q1401220"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753015$F74EF8EA-2255-47F4-B1FF-4283DA129DAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4639d3f4b2f5c3f2fcad6901021a5308c5155800","datavalue":{"value":{"entity-type":"item","numeric-id":2380272,"id":"Q2380272"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753015$29CD32D1-60D3-4332-A3F7-311FF37CAD24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"77515ffb25d5fd8b5cf083d6e4383d73817b73c1","datavalue":{"value":{"entity-type":"item","numeric-id":2446882,"id":"Q2446882"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753015$85603BC5-F406-42AE-9B40-47A855085F14","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c6e797c46aae7be0c6915e03105d8e7fa97a7fec","datavalue":{"value":{"entity-type":"item","numeric-id":526246,"id":"Q526246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753015$F6B1DD9F-2DCF-4551-953A-27E8C825D6C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c9972a4977a5a11aa1649a275229853eb58be483","datavalue":{"value":{"entity-type":"item","numeric-id":5920174,"id":"Q5920174"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753015$D7B95D1C-8785-4B30-B9AC-0C978283E39B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"82b6344e3addf5ad68c758a5b1bb61a85aa49ab7","datavalue":{"value":{"entity-type":"item","numeric-id":2018540,"id":"Q2018540"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753015$4DDCAC91-68F8-4579-9980-EC039AA40655","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4539515bafb50ac7b079d0e4f74fc6c1a9953bf5","datavalue":{"value":{"entity-type":"item","numeric-id":5325952,"id":"Q5325952"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753015$271B6B48-999C-41CB-869B-205BEC303747","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"88b428cfd1e9864f827faf01b05b33ef87cd71b5","datavalue":{"value":{"entity-type":"item","numeric-id":2430979,"id":"Q2430979"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753015$45768C40-E00F-40A7-87DB-A6CDD357C30C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753015$BB16873B-9242-4B76-9F68-ED4AAF3196B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b382547d8fad964f6c32dd98e9936f8afb92f192","datavalue":{"value":{"entity-type":"item","numeric-id":1230637,"id":"Q1230637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753015$56DA979D-A7FB-44C6-BBBA-4D572553E2A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"75550638858b151dfc69ee7585c35c3357079f4d","datavalue":{"value":{"entity-type":"item","numeric-id":864130,"id":"Q864130"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753015$2CFDB92C-2712-4DC6-821F-E0381941E4B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"501aefe4754342fb8d5444baacca037714207964","datavalue":{"value":{"entity-type":"item","numeric-id":4999425,"id":"Q4999425"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753015$FA1AD0A3-0DDA-40CE-96A3-803277AB5758","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ee1ec3e679277531ddeee1652cd1faae98a96c8f","datavalue":{"value":{"entity-type":"item","numeric-id":4400275,"id":"Q4400275"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753015$2BF18415-9E9D-4349-9428-A88E682526C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d50041fd827b9a880db5475227f379529c471731","datavalue":{"value":{"entity-type":"item","numeric-id":790612,"id":"Q790612"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753015$957005D1-A1B8-4271-B918-28BBF8FD3436","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"a772d35bf81c083b11e08cafdd1ac503e5118497","datavalue":{"value":"bafkreifqd6ekc75hu57qulqyh657b3v32wbn5kov3hoam3mutldrieqnpi","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1753015$4DDF40B7-E1B3-4FCC-9B96-8F6A9393306A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2840413cdbf3aa0a1751a9cbd2152c6a067b445c","datavalue":{"value":{"entity-type":"item","numeric-id":1401220,"id":"Q1401220"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"40128ec7362f44c7a25a3d5d4b5016c738dac521","datavalue":{"value":{"amount":"+0.8251540660858154","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":"Q1753015$4EC582C7-FA5C-41F6-87BB-F33E2DBCD392","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"99659d13d227fe9538c9b4f138952d0efd5c04dd","datavalue":{"value":{"entity-type":"item","numeric-id":2851521,"id":"Q2851521"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bc3763970cf7941fbd4ec0cb5f51b9bdf94bc72a","datavalue":{"value":{"amount":"+0.8234262466430664","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":"Q1753015$88AD8889-D09A-412C-8100-6957B33BF3F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"68a97cb9e9476a2a5310ca6c9c04569751e2f61c","datavalue":{"value":{"entity-type":"item","numeric-id":976158,"id":"Q976158"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5ebec33e45248f7195a81908df6e4ef83a7bcf99","datavalue":{"value":{"amount":"+0.809391438961029","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":"Q1753015$2C418CA8-2A62-45E0-B440-88B067DCC1EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6043a46a6d4568b1cbfaffc8d9fed3a1dd9e53dc","datavalue":{"value":{"entity-type":"item","numeric-id":2189840,"id":"Q2189840"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9f3f47a614df05a26cc9c756bf1d1155f289a008","datavalue":{"value":{"amount":"+0.8092280626296997","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":"Q1753015$40F6BB94-8480-45C6-BA4D-2E1B5D5DA99E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"28186029cd1220ac71d6f8e5be895483199d46a6","datavalue":{"value":{"entity-type":"item","numeric-id":423972,"id":"Q423972"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b5938b2eb123356842a067b050f92cbdb783e2cf","datavalue":{"value":{"amount":"+0.8079214096069336","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":"Q1753015$94EA5B63-8F39-4FCE-BDA0-F380EEADF29A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the minimum size of an identifying code over all orientations of a graph","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_minimum_size_of_an_identifying_code_over_all_orientations_of_a_graph"}}}}}