{"entities":{"Q1953340":{"pageid":1964082,"ns":120,"title":"Item:Q1953340","lastrevid":51733868,"modified":"2026-01-19T18:10:35Z","type":"item","id":"Q1953340","labels":{"en":{"language":"en","value":"Identifying vertex covers in graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6171815"}},"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":"Q1953340$6BEAFCD3-97F4-4DF2-BEEA-D18B6EC52951","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2f841860c0735e8fa9993647cac8d649e9479cf0","datavalue":{"value":{"text":"Identifying vertex covers in graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1953340$3447EE33-AD73-43CF-9BCA-E3F64C7B20FF","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3c6d384026c7acf32ff492122152d831f0ac06ce","datavalue":{"value":"1266.05118","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1953340$006C98EB-0F21-47D3-8CB5-8EBAB63CC885","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1ef3efb47b5163e35efff4dde79a3bbdd3dc566b","datavalue":{"value":{"entity-type":"item","numeric-id":186200,"id":"Q186200"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1953340$DE13D767-8DF6-48F6-9AF1-758437B4399C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ce446809cda0969b939786a794eae79a100b8b76","datavalue":{"value":{"entity-type":"item","numeric-id":168085,"id":"Q168085"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1953340$D75098D1-9DEB-4DA4-A761-1B9E851407DB","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":"Q1953340$A53120D8-66D9-4527-9106-8583FD37F3A3","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"4a8303ee696998ba030c9b1c3b6bc07c6038c334","datavalue":{"value":{"time":"+2013-06-07T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1953340$B9BCE010-FDCB-4F5A-90B4-2F92A77EE827","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a223b947c7e4dadf3d0ad43d10bf07f11086d726","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v19i4p32","type":"string"},"datatype":"url"},"type":"statement","id":"Q1953340$4B2723F0-7468-4654-80E3-81587A4949C5","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"dd6f0e21a75e5b71349830086b830663ba6be914","datavalue":{"value":"Summary: An identifying vertex cover in a graph \\(G\\) is a subset \\(T\\) of vertices in \\(G\\) that has a nonempty intersection with every edge of \\(G\\) such that \\(T\\) distinguishes the edges, that is, \\(e \\cap T \\neq \\emptyset\\) for every edge \\(e\\) in \\(G\\) and \\(e \\cap T \\neq f \\cap T\\) for every two distinct edges \\(e\\) and \\(f\\) in \\(G\\). The identifying vertex cover number \\(\\tau_D(G)\\) of \\(G\\) is the minimum size of an identifying vertex cover in \\(G\\). We observe that \\(\\tau_D(G) + \\rho(G) = |V(G)|\\), where \\(\\rho(G)\\) denotes the packing number of \\(G\\). We conjecture that if \\(G\\) is a graph of order \\(n\\) and size \\(m\\) with maximum degree \\(\\Delta\\), then \\(\\tau_D(G) \\leq \\left( \\frac{\\Delta(\\Delta - 1)}{\\Delta^2 + 1} \\right) n + \\left( \\frac{2}{\\Delta^2 + 1} \\right) m\\). If the conjecture is true, then the bound is best possible for all \\(\\Delta \\geq 1\\). We prove this conjecture when \\(\\Delta \\geq 1\\) and \\(G\\) is a \\(\\Delta\\)-regular graph. The three known Moore graphs of diameter two, namely the 5-cycle, the Petersen graph and the Hoffman-Singleton graph, are examples of regular graphs that achieves equality in the upper bound. We also prove this conjecture when \\(\\Delta \\in \\{2,3\\}\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1953340$8AD95EFF-8E14-4329-AA36-76C061F8C911","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1953340$3427D8B9-FE13-4DFD-9536-7CD31F368991","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1953340$C7A0A62C-ADF4-4254-BB55-D1D556B02D3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1ad1bf428b79a0176d62afa9a160b2a17f8d9ea9","datavalue":{"value":"05D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1953340$C7D0DB23-6614-487E-9ED0-032763E58D70","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"bb4d26bee03f9ecaae77e1b5d3319ad186719313","datavalue":{"value":"6171815","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1953340$F859A80A-A10A-4D28-85EF-B4FEAAF9C159","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"aac385c43cc6d982a9dd1fbfee8ab2754a681c11","datavalue":{"value":"vertex cover","type":"string"},"datatype":"string"},"type":"statement","id":"Q1953340$668FD61A-1F97-482E-9DF3-DBDB5B5E7760","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"15c62e1455ab113f67bcf805beb7e272e5d60987","datavalue":{"value":"identifying vertex cover","type":"string"},"datatype":"string"},"type":"statement","id":"Q1953340$FBECA2A4-33DC-4F7B-9BFF-A97AA0EFF033","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"916cdd3d2a6f5f57db6bd562990e6d44b7fb3b1d","datavalue":{"value":"transversal","type":"string"},"datatype":"string"},"type":"statement","id":"Q1953340$37CECBD1-4616-482E-9447-BB302AFFDB8C","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":"Q1953340$989E4B5E-CF34-421A-826A-396117FDD6F5","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"e69e6ebbbb2632800508c6ee432126b6da7ae1d9","datavalue":{"value":"bafkreieacvf6htsfdvbhpswtgjdczmdp2jfmcgqaubymljfsilu63ve3ai","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1953340$882A8379-885E-4B24-A15C-FB0D2109C3CA","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"acbbdd919e969e42edfb32944bc49071a763d75c","datavalue":{"value":{"entity-type":"item","numeric-id":426794,"id":"Q426794"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3c524dbe82a8c5716063d4abf2e00a48918aca85","datavalue":{"value":{"amount":"+0.7670642733573914","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":"Q1953340$2508B54D-A3D1-41CB-838A-BE7610371823","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"90be1c0015c5448a1396b31803c59fc17e54f41a","datavalue":{"value":{"entity-type":"item","numeric-id":2430979,"id":"Q2430979"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"35819760a267ef9c0733f62ee2da40993b67ab1e","datavalue":{"value":{"amount":"+0.7603933811187744","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":"Q1953340$F6BC7417-49FF-435A-AF2F-0DDD5FBE9A51","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"54723e1dff9efd845f0eeb66f31ab7e92b5b1fc4","datavalue":{"value":{"entity-type":"item","numeric-id":396675,"id":"Q396675"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cf6ba203e70d470a6260e805e075f271bb780808","datavalue":{"value":{"amount":"+0.7580493688583374","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":"Q1953340$AAABF9EB-0F52-47A2-8478-5F6C1F72AF40","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0d1e491cff3648ef20363a27a2a1f137938171af","datavalue":{"value":{"entity-type":"item","numeric-id":2876554,"id":"Q2876554"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bdffe81952ba5c57078a007be49f709e323e7474","datavalue":{"value":{"amount":"+0.7531088590621948","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":"Q1953340$96A512F2-4158-4F1C-9804-1C191D9BE9DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"07740fc72544ac3e3cd12bdd315f84550af86213","datavalue":{"value":{"entity-type":"item","numeric-id":4024338,"id":"Q4024338"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c1aff51d1021d79781d594d53377b5be6c5bc960","datavalue":{"value":{"amount":"+0.750423789024353","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":"Q1953340$3C081836-8310-4B29-867F-B5216E97EA18","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1953340","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1953340"}}}}}