{"entities":{"Q2761050":{"pageid":2771789,"ns":120,"title":"Item:Q2761050","lastrevid":47713555,"modified":"2026-01-02T12:26:13Z","type":"item","id":"Q2761050","labels":{"en":{"language":"en","value":"An inequality characterizing chordal graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1682912"}},"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":"Q2761050$A829BED1-6E23-455B-85EC-F4CF10E53301","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"704646f8712717d814c520953221437c63d3231c","datavalue":{"value":"0977.05110","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2761050$F3872131-DE5F-44A3-BD7E-82F8C6055026","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"703b1f79ea71713ba8c8eda07544b2290c123390","datavalue":{"value":{"entity-type":"item","numeric-id":376560,"id":"Q376560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2761050$316AC434-F65A-4FDC-B661-16FAA00F6663","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"dd43b7556960d36e19e31bfdf153901cadf12bc7","datavalue":{"value":{"time":"+2001-12-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2761050$2D8AE444-F232-4360-BBD3-8A1A5DB695C0","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2761050$5F6DD391-D6F6-4A92-B1B5-EB175372C8EA","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a0801e7dfcc0bf654480bfce765bc91e74362a1c","datavalue":{"value":"1682912","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2761050$02994747-8527-4F5B-BF43-649FBACDF468","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dae41303426e6695786e3a6d28699919bfeab34a","datavalue":{"value":"chordal graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2761050$7172C690-52BA-4E66-B4C6-BB330A8BE23F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a794051be85d5b93e047b98f2a96808b1a88edec","datavalue":{"value":"connected component","type":"string"},"datatype":"string"},"type":"statement","id":"Q2761050$EFA127DF-C01B-4444-BAFE-3D4A86E6B7DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7afa3f68fa61c626ce66f4eae31dc94c27dbba54","datavalue":{"value":"dominating number","type":"string"},"datatype":"string"},"type":"statement","id":"Q2761050$54BEB216-909E-46A4-ABBD-67E2D0862CC6","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":"Q2761050$E5D74C09-EA84-4EEA-BB18-9AC470B7AB03","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5f54805d67d2971d44f13d47401318ef7d50e9c8","datavalue":{"value":{"text":"An inequality characterizing chordal graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2761050$52E67806-DB67-48CF-B47C-FDD7489C21C1","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"6f7fbf6651880b9d76c5e78437f7f8284b8f74c4","datavalue":{"value":{"entity-type":"item","numeric-id":6550664,"id":"Q6550664"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2761050$1F2EB5B2-CA96-4316-A1A7-6443DF6ED33F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"fe819b3a2bd5684e66b6d78194395bdc51028697","datavalue":{"value":"A graph is chordal if every cycle of length at least four has a chord. A new characterization of chordal graphs is given, as graphs that satisfy equality in the inequality \\(\\sum_Q(1-\\text{comp} N(Q))\\leq \\text{comp} G\\), where the sum is taken over all nonempty complete subgraphs \\(Q\\), \\(N(Q)\\) denotes the set of vertices adjacent to all vertices of \\(Q\\) and \\(\\text{comp} G\\) denotes the number of connected components of \\(G\\). The inequality is also established. The concept is extended to more general graph parameters and it is shown, e.g., that \\(\\sum_Q(1-\\gamma (N(Q)))\\leq \\gamma (G)\\) (where \\(\\gamma \\) denotes the dominating number) holds for any graph \\(G\\), while equality holds exactly for \\(P_4\\)-free chordal graphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2761050$4C61F50D-FB1A-42D0-86FC-423A88828930","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6f06fe55d6bc156d465871e5ec7b1e3c52e3687b","datavalue":{"value":{"entity-type":"item","numeric-id":3804748,"id":"Q3804748"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dee497777e4198fd56b292418828b340390ac32b","datavalue":{"value":{"amount":"+0.7925784587860107","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":"Q2761050$87D398A2-C35D-4A82-BD59-CBFAFAFF333C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4e7e58616e120257ec43993599d8fac73c81b4a9","datavalue":{"value":{"entity-type":"item","numeric-id":1174126,"id":"Q1174126"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"09b71c81375269702d60c4a6211fcc0834a55d6c","datavalue":{"value":{"amount":"+0.7695586681365967","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":"Q2761050$455717E1-830D-40B9-A451-E30430DD2D06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"58dd1439520e0aa60e770864dd249a228420ca39","datavalue":{"value":{"entity-type":"item","numeric-id":2366014,"id":"Q2366014"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cbe86be8c0004bde0001717497ce53847f3ce3bc","datavalue":{"value":{"amount":"+0.7636375427246094","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":"Q2761050$EE89C16A-DD49-4A62-832F-BE12D20495B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d8ddc8299bbef976c701746b0cc1166e26d70e4e","datavalue":{"value":{"entity-type":"item","numeric-id":1376068,"id":"Q1376068"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b451b635c2580aff8206a472708ceecc60ae3899","datavalue":{"value":{"amount":"+0.7621899247169495","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":"Q2761050$50F7513F-76C7-43F9-8874-49563FDE08FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b9f08b6e1a573c988fa91ffbbfe81deb844ac8b6","datavalue":{"value":{"entity-type":"item","numeric-id":394280,"id":"Q394280"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8ce6d96b3a247568715d90a8fdfb6f4caaa7f420","datavalue":{"value":{"amount":"+0.7606806755065918","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":"Q2761050$530E9D4B-6DBC-47F6-A681-F29B6E87AE2E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2761050","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2761050"}}}}}