{"entities":{"Q1613565":{"pageid":1624305,"ns":120,"title":"Item:Q1613565","lastrevid":72345543,"modified":"2026-04-14T04:16:51Z","type":"item","id":"Q1613565","labels":{"en":{"language":"en","value":"A disproof of Henning's conjecture on irredundance perfect graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1792480"}},"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":"Q1613565$7ECBECD2-1C20-4298-ADE9-7E1C6E0C9D42","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"397e266cc65ed3803f472300c353aa2234eb594a","datavalue":{"value":{"text":"A disproof of Henning's conjecture on irredundance perfect graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1613565$F6D024A2-C251-4929-B0D6-500DF57DE60F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"47aebe8db8c9d154406684f9c406be2be0434ee8","datavalue":{"value":"1008.05073","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1613565$8B6C3924-18C8-4F39-9142-6171D33FDCE9","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d5036389c945b8a58f16f5b16d79b81ab853a803","datavalue":{"value":"10.1016/S0012-365X(01)00300-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1613565$0A513D16-0575-422E-A82C-11CC5AD2B39E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9b4422e37ea985f640d4cbfe3c8456c60e8e83e9","datavalue":{"value":{"entity-type":"item","numeric-id":186197,"id":"Q186197"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1613565$D3D84E6D-A385-4B84-9566-7AEB0B21FFB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"63b7ce1831c38fbe17eea7f63888fd121d156aa9","datavalue":{"value":{"entity-type":"item","numeric-id":1270642,"id":"Q1270642"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1613565$F2ABF274-E387-47A3-AE1B-1EA7277F508C","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":"Q1613565$8CB4A48A-C3DA-4FFC-9244-303AA2C684C9","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"04ef60e6a08d63a03521c7b80b58e0a998b63b55","datavalue":{"value":{"time":"+2002-08-29T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1613565$D722C445-82B2-410F-B95C-AD31296037AC","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c44110940045a16396c52e8a74f9deaaffb1cbb8","datavalue":{"value":"The paper leans on the following notions of finite simple undirected graphs. The domination number of a graph \\(G\\) is the minimum size of a vertex set \\(X\\) such that any vertex of \\(G\\) is either in \\(X\\) or is adjacent to some vertex of \\(X\\). Vertex set \\(X\\) is irredundant if for each vertex \\(x\\) of \\(X\\) either \\(x\\) is not adjacent to other vertices of \\(X\\) or there is a vertex \\(v\\) of \\(V(G)-X\\) such that \\(v\\) is adjacent only to \\(x\\) in \\(X\\). Irredundance number \\(\\text{ir}(G)\\) is the minimum size of an inclusionwise maximal irredundant set of \\(G\\). A graph \\(G\\) is irredundance perfect if \\(\\gamma(H)=\\text{ir}(H)\\) for any spanned subgraph \\(H\\) of \\(G\\). After introducing some reladed notions, the authors survey some results on irredundance perfect graphs. They formulate Henning's conjecture saying that a graph \\(G\\) is irredundance perfect if each spanned subgraph \\(H\\) of \\(G\\) with \\(\\text{ir}(H)<5\\) is irredundance perfect. The main result is a counterexample to this conjecture, namely a concrete minimal irredundance imperfect graph \\(F^*\\) with \\(\\text{ir}(F^*)=5\\). (The authors seem to have a computer aided proof for the imperfection property.) The disproof of the conjecture is a labourious case check. The complexity result in the paper is that the irredundant set problem and the dominant set problem are both NP-complete for a certain subclass of irredundance perfect graphs. The article ends with some conjectures and problems.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1613565$961494D4-EFB3-439D-933F-2C90C9536E07","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"d4de3193b89da1a841d76ad5faa949e9be96ad30","datavalue":{"value":{"entity-type":"item","numeric-id":228803,"id":"Q228803"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1613565$CB02AD08-46E8-492B-BB5B-4849693FDB3C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e409eb44902873893a0f6988ee9577058bcb2578","datavalue":{"value":"05C17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1613565$AAC073CD-B31A-4C99-9074-5FC6D56FAB07","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1613565$16120599-DBCB-4A3C-A45C-6B1AC140D676","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1613565$C38BFB40-8085-4FB8-A55B-E14298CB2082","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"bfe80de0b7f8dfcb1b1b72fd995b1615f2fed5bf","datavalue":{"value":"1792480","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1613565$41996B9E-4F9C-440C-960D-11AA4C417DCB","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3267d14ab3c644208190b057ee58cacbeb7fa5c7","datavalue":{"value":"domination number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1613565$AEA5C1DC-11E0-41D1-9FF9-5E774549C688","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7e513be6891ec70459e0ac428db4a76b8e757466","datavalue":{"value":"irredundance number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1613565$9AA06317-57D3-45A5-B599-03E84167A07B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0edcab7136638c2f63f511b29c2c0b74116e2fb9","datavalue":{"value":"irredundance perfect graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1613565$A62EAF37-390B-463D-BA7C-5A03A019806E","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"1ecb5a8674964b7ede91029422fa5bf8d613fea8","datavalue":{"value":"Q123019300","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1613565$E22D051C-63E8-4FB3-8453-0C678EF8BC52","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":"Q1613565$59BDE911-F591-4980-87FC-8FB546E07F00","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9ed1746aa4513572db473534847263dd01ed8fb0","datavalue":{"value":{"entity-type":"item","numeric-id":4798120,"id":"Q4798120"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e5c54f214eab0c6755f7ac2ed5e2ea4e289e34d3","datavalue":{"value":{"amount":"+0.9298794","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1613565$C06EB1D9-33BB-44A6-88C7-D0D2741ED478","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5a5921d3aa0ec6b99e083af8308ec1d7696eee37","datavalue":{"value":{"entity-type":"item","numeric-id":5298905,"id":"Q5298905"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1402fcda6d052b54f07bf57cd2b58d0a556dc438","datavalue":{"value":{"amount":"+0.8946636","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1613565$5B3A1712-0B8F-4AD1-AE5D-F6A30079D32B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0308a36b5fe000a847dda1aded2161d1063e21a1","datavalue":{"value":{"entity-type":"item","numeric-id":4943531,"id":"Q4943531"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2db7c7fbb22e219345411ad4d896dfabbbfe411a","datavalue":{"value":{"amount":"+0.8883564","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1613565$6BA05FBF-F79A-4810-8E3C-097C872A28B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c10d26e208155c255e7ae7177c2f8567c1cd9b98","datavalue":{"value":{"entity-type":"item","numeric-id":686172,"id":"Q686172"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"49c25d61781f3f9acc91ceb80b6abe8146ae4e90","datavalue":{"value":{"amount":"+0.8822791","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1613565$26C696A8-36FE-45A2-A539-F60364E11D1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0f79a6d276a89e761bf71da7e9f20466bf024abf","datavalue":{"value":{"entity-type":"item","numeric-id":1896349,"id":"Q1896349"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6cfc2eae248075bfc0448f33c6f332ca7ee5cd1e","datavalue":{"value":{"amount":"+0.8805307","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1613565$CE07B1D3-0969-49EE-B607-E4EDF3FB2511","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ce904569b2f60ab00ce52d9eb9869797b8e5094e","datavalue":{"value":{"entity-type":"item","numeric-id":4522468,"id":"Q4522468"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fafb0eb3efeea0340fe0dfb46ea88a46f13e6348","datavalue":{"value":{"amount":"+0.87680525","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1613565$DD1B7C19-9001-4139-84C7-8D4945B639C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"95fedf6fe08921d93c9ef62d0dd3fd93a3040979","datavalue":{"value":{"entity-type":"item","numeric-id":1248633,"id":"Q1248633"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5fbd1962380e30a5628a784e3426017b6b0e7450","datavalue":{"value":{"amount":"+0.8748166","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1613565$8BCE3AF9-1A7D-4DC4-A557-31A46C564151","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"763337813b04689ffa74c8005264e336cdbd0f82","datavalue":{"value":{"entity-type":"item","numeric-id":5103798,"id":"Q5103798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e30c30b790b679c840fbb9d35e8b30e7fb5789b9","datavalue":{"value":{"amount":"+0.869268","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1613565$870D913C-73EE-4149-802C-DEC214994641","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"203fa97978861a4bc01d10ffab050fb275851f4b","datavalue":{"value":{"entity-type":"item","numeric-id":2721336,"id":"Q2721336"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dfb5441f7370b8388381308f8b05bc07a24e8219","datavalue":{"value":{"amount":"+0.86892676","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1613565$2EE474A5-A297-49C0-9FDB-B9DF74A8C5DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cf5f676fd9aea3cfc8de40975ef9934d2186ab6e","datavalue":{"value":{"entity-type":"item","numeric-id":5948970,"id":"Q5948970"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7515db4538a39971e84dc5d72c51c2d702f4497e","datavalue":{"value":{"amount":"+0.8652623","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1613565$7097C46E-0AF0-4A0C-9443-D69E7AAF3FAE","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A disproof of Henning's conjecture on irredundance perfect graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_disproof_of_Henning%27s_conjecture_on_irredundance_perfect_graphs"}}}}}