{"entities":{"Q1322189":{"pageid":1332939,"ns":120,"title":"Item:Q1322189","lastrevid":70707087,"modified":"2026-04-13T16:16:16Z","type":"item","id":"Q1322189","labels":{"en":{"language":"en","value":"Dominating cliques in chordal graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 562597"}},"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":"Q1322189$84C76056-0C1B-4965-9439-799E0919D5CB","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d571c3356c27414e508f25d92f97ee0cd817f074","datavalue":{"value":{"text":"Dominating cliques in chordal graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1322189$14ED6D13-A336-43C6-B94D-7F2A3DEE4903","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"bf6c69844bb586bfb86b873f677caa1756dd8f57","datavalue":{"value":"0796.05052","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1322189$827C69E6-1FD0-48BB-838D-CB7EE6FC3786","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"99f2ebb92d11f63c0e15a039b08e3cce36344c80","datavalue":{"value":"10.1016/0012-365X(94)90118-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1322189$20CA1208-9945-417C-813A-D1FD4BC01ED2","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5adf86a269713b0e23511a52caceaa2ff6312793","datavalue":{"value":{"entity-type":"item","numeric-id":190506,"id":"Q190506"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322189$93613F52-23C8-4795-BE69-FCF235DCAFED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"efc35cf3e0639840fea360bd5e9b46c46abc9a77","datavalue":{"value":{"entity-type":"item","numeric-id":169283,"id":"Q169283"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322189$9168F50A-35CF-48A8-8FE5-AB59D8641FC1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"938137206edfdd9a5ca2b52193c40f9e98ed806d","datavalue":{"value":{"entity-type":"item","numeric-id":293262,"id":"Q293262"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322189$D9D9EC2E-9BCC-446C-86DE-EB0D676DC4FA","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":"Q1322189$1C6772DB-CAC0-40A5-8F47-FD86EA63928D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d79d7cda91904207155cc49e8915318cb6203fb9","datavalue":{"value":{"time":"+1994-09-15T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1322189$2613DFB1-5470-4C72-BC7A-C05D008559E0","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"247a6fc90fa6270513fd588e24b591890d171f79","datavalue":{"value":"A graph \\(G\\) is chordal if every cycle of length exceeding 3 has a chord, i.e. an edge joining two nonconsecutive vertices in the cycle. A chordal graph is called strongly chordal if every cycle of even length exceeding 5 has an odd chord, i.e. a chord joining two nonconsecutive vertices of odd distance apart in the cycle. This paper proves that a chordal graph has a dominating clique iff it has diameter at most 3 and proves (by means of a linear-time algorithm) that a strongly chordal graph which has a dominating clique has one as small as the smallest dominating set.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1322189$A6B7522D-D48C-4633-BC3A-11C725696546","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1322189$7F90D8AB-6331-40E1-B10D-4F02EB3B01DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1322189$AD0CA157-05F1-4311-B202-FA2D3EBA8A03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1322189$71FF7F2C-0A53-41CA-A2C1-2E984F2B0ECA","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3c091f4ffb8c3488170fc881c49d2123fad4b52c","datavalue":{"value":"562597","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1322189$08D41C48-38CC-4673-9FC7-50EC103D15E4","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"440b14f881817b10d08f3f9446a28d845a2252c1","datavalue":{"value":"chord","type":"string"},"datatype":"string"},"type":"statement","id":"Q1322189$340C867A-F9FB-46B9-A1E8-439242551E73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1ae6cc52b35d03b83d5162d854c61cf5b039329e","datavalue":{"value":"cycle","type":"string"},"datatype":"string"},"type":"statement","id":"Q1322189$0CAAC0DD-1CA8-4C1B-9EBD-C2313A5B9755","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dae41303426e6695786e3a6d28699919bfeab34a","datavalue":{"value":"chordal graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1322189$0D718D7E-B8E8-4E55-B0B3-4B0C00E293E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bcabe08102492dc2cd54fa9819cb8eea09efdacc","datavalue":{"value":"dominating clique","type":"string"},"datatype":"string"},"type":"statement","id":"Q1322189$9F3CE0A6-A89C-409E-9F87-22F640B35FA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cd227adb1378edbe90691dff18511cebed6b0036","datavalue":{"value":"diameter","type":"string"},"datatype":"string"},"type":"statement","id":"Q1322189$0F92FB5C-3882-4274-83A5-C16D1BA8AAE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"124ac1722fe734ef47798ef941038677e84e92b3","datavalue":{"value":"strongly chordal graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1322189$F55629E5-D396-4BCB-B0FF-CD762863A966","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"210f6e878bc06e635be406e25541c4c590749f5e","datavalue":{"value":"dominating set","type":"string"},"datatype":"string"},"type":"statement","id":"Q1322189$248E7C32-3DE6-4E23-94AB-C57869D51B13","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":"Q1322189$EFD5F164-E78F-4EA6-9592-07132D712FAC","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"09b06ada4a02303c79d7ffc00581d47956a243d6","datavalue":{"value":{"entity-type":"item","numeric-id":4099676,"id":"Q4099676"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322189$D6A67E5D-3AC1-4539-96B3-7740BC86A471","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b6ba8beca23cdaad0ac4c8fdb9394466e17ade7f","datavalue":{"value":{"entity-type":"item","numeric-id":1051004,"id":"Q1051004"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322189$0C2EED81-5EAA-45DD-B512-F1B309372B18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d20d43981ea8728a5c02a1bf60e0f2b91181b43","datavalue":{"value":{"entity-type":"item","numeric-id":788002,"id":"Q788002"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322189$3C4A67A2-C7F2-4D56-A263-DDAC48A09312","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e458531dc8f9b4a4f76ca8cb6a5d9d31ac768ee2","datavalue":{"value":{"entity-type":"item","numeric-id":2562090,"id":"Q2562090"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322189$F277E773-9BE6-4B8F-B4BF-7DB24DABDF3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b49197929288f9de080d26326dbced0d14b3ab6c","datavalue":{"value":{"entity-type":"item","numeric-id":804605,"id":"Q804605"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322189$59227C8E-6F14-401B-BCA1-057EE7C415C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2bcba5248e140fbf35104315fa1eae1d8cb49705","datavalue":{"value":{"entity-type":"item","numeric-id":3997600,"id":"Q3997600"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322189$F24B3274-4A40-4D53-BA94-12BC9671A692","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9c599904edd4b855eecaa19378a025317a7387eb","datavalue":{"value":{"entity-type":"item","numeric-id":805638,"id":"Q805638"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322189$62E7062C-0EF0-4E7D-B87C-E8A95A6CC29F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e0ba1d687a45ea9b6660e43c3eb9d43b1d106ece","datavalue":{"value":{"entity-type":"item","numeric-id":3696538,"id":"Q3696538"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322189$E7E8B9D3-A20F-4CF2-9555-564EC45ACE99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3c774834971b086c761bf1be38a21a13366e3f9d","datavalue":{"value":{"entity-type":"item","numeric-id":3758873,"id":"Q3758873"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322189$5AABC01F-B44A-474F-8586-C62874856352","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"df3760ef905d3060c54dda93d12d2f3a43417a40","datavalue":{"value":{"entity-type":"item","numeric-id":5896554,"id":"Q5896554"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9598cd16276da9793d88163908f7a1723cadc43a","datavalue":{"value":{"amount":"+0.95267904","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1322189$CEF477D4-7D84-4A11-8CFD-D5EF7433B45E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0905548df64f2015ae1331bf99918b68d8346d5a","datavalue":{"value":{"entity-type":"item","numeric-id":5925264,"id":"Q5925264"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9598cd16276da9793d88163908f7a1723cadc43a","datavalue":{"value":{"amount":"+0.95267904","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1322189$B5B23CC8-549A-4BE5-B39E-702149F70DB5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5ec6f28da156775aa34fe60f8e85efecc0464cc9","datavalue":{"value":{"entity-type":"item","numeric-id":805638,"id":"Q805638"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"966a0ed0fbb5b281e69b99a52bae73af08b3218c","datavalue":{"value":{"amount":"+0.932447","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1322189$C9C6385D-2C9D-461D-B8A5-2D0C8F3B6AD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c0ac5fcad9b9971fc17c692d8f0fb0a6f1dffc28","datavalue":{"value":{"entity-type":"item","numeric-id":4847026,"id":"Q4847026"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"817810e1c4326d38b748ae7e4ddd65aa1eb43700","datavalue":{"value":{"amount":"+0.91835827","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1322189$06C780F8-1D36-4CA6-9195-606833DF940A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"950e78328b1412029800caecf299475de934874a","datavalue":{"value":{"entity-type":"item","numeric-id":3035328,"id":"Q3035328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bd471a7c75f080b476a706d0dabff63351aa27ed","datavalue":{"value":{"amount":"+0.91460407","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1322189$5887F58A-0AE9-4573-A1E2-7AC4B02E6C4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"346ca7a8cc124e7238d6cfc4c65d7c84bf78251f","datavalue":{"value":{"entity-type":"item","numeric-id":2760993,"id":"Q2760993"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f3d66c7e40d20ec1da14f85eda21487f7732745c","datavalue":{"value":{"amount":"+0.91136134","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1322189$D6B8CF19-5B5E-487E-ADD9-D10489943DB1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"059c1791779f208d6fa5e05d674dc354bbbb9474","datavalue":{"value":{"entity-type":"item","numeric-id":3115054,"id":"Q3115054"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"42775c3a288b2bfa0c1f0a73a0f72b618405ed28","datavalue":{"value":{"amount":"+0.909364","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1322189$53650B8B-0595-4178-B21C-E96F4B185DAE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bde40ad04c9e7aa28f92e3ab31afb7e125f60f5d","datavalue":{"value":{"entity-type":"item","numeric-id":918703,"id":"Q918703"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"18585fe894bcd76ab8f98c2ed45f634710538445","datavalue":{"value":{"amount":"+0.90908736","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1322189$D3B899A2-C72A-495F-A52F-6D1B40BD7B22","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"48d70a785275c193bf59eed4abe721158ba96209","datavalue":{"value":{"entity-type":"item","numeric-id":5401055,"id":"Q5401055"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"57568ada240932dc5e46d0569d3f1cfabcead570","datavalue":{"value":{"amount":"+0.90759826","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1322189$ED0C6C60-B3E9-434F-A3F6-0EF90C13FBA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ce27258a98383b55ff7c1aefd9ba4428ed565d90","datavalue":{"value":{"entity-type":"item","numeric-id":1910588,"id":"Q1910588"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eeb0e776ab1b390584e81edf12a18b3d24aecb3a","datavalue":{"value":{"amount":"+0.9072729","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1322189$C2ACFA98-D390-4F75-B9E6-3C212361C8BE","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Dominating cliques in chordal graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Dominating_cliques_in_chordal_graphs"}}}}}