{"entities":{"Q1868852":{"pageid":1879594,"ns":120,"title":"Item:Q1868852","lastrevid":73593525,"modified":"2026-04-14T16:35:00Z","type":"item","id":"Q1868852","labels":{"en":{"language":"en","value":"Chordal graphs and the characteristic polynomial"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1901901"}},"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":"Q1868852$82E7F99A-CF27-4246-9F39-CB47B7BF0FE9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"667c74f536b6f0e953690d7a28e6a38c64109917","datavalue":{"value":{"text":"Chordal graphs and the characteristic polynomial","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1868852$7A52453F-EF45-4606-9C6A-90611361701D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ca8d75090524d663ec2451acdd1698fd0d564f5a","datavalue":{"value":"1017.05059","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1868852$AF4217A5-9019-4D78-93D6-1CBC1C4770C3","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b0df3b748097495e379b70e2857ace28607b673a","datavalue":{"value":"10.1016/S0012-365X(02)00500-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1868852$05008A6D-C1B8-4F29-9B65-9F8F121B0C4A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"40a111d89e39446d5e85a0cf1846c34b81b2ffeb","datavalue":{"value":{"entity-type":"item","numeric-id":1868849,"id":"Q1868849"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1868852$59A4AEF4-F458-402E-82B9-198B76761609","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"10dcf151efb4a168762155bea70ffcf20cad3977","datavalue":{"value":{"entity-type":"item","numeric-id":1868850,"id":"Q1868850"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1868852$D6C3E8C4-AD7F-46DE-90FB-F8B6F2FBED89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"82e5c8bee09c405a2e94b5753c9f95744ea20286","datavalue":{"value":{"entity-type":"item","numeric-id":1868851,"id":"Q1868851"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1868852$D84F09DB-B463-4C37-AC4D-A9103DDBAEC3","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":"Q1868852$CC6CE680-60FB-410D-BFE2-8320442EA41A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3b05751a28df8b7d171e02c18dec5082d33efa41","datavalue":{"value":{"time":"+2003-04-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1868852$3479B730-378B-4802-96AC-6E9B83309B78","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0336bd65bd1fcf5f970cb5b25b58ef75e28d775b","datavalue":{"value":"The greedoid ``characteristic polynomial'' is studied for greedoids (anitmatroids, in this case) which arise from chordal graphs. The greedoid two-variable ``Tutte polynomial'' of Gordon and McMahon is, for a greedoid on \\(E\\) having rank function \\(r\\),  \\[ f(t,z) = \\sum_{S \\subseteq E} t^{r(E) - r(S)} z^{|A|- r(A)}. \\]  The greedoid ``characteristic polynomial'' is then \\(p(\\lambda) = (-1)^{r(G)}f(-\\lambda, -1)\\) (not to be confused with the one-variable ``Tutte polynomial'' \\(\\lambda(t) = f(0, t-1)\\) of Bj\u00f6rner, Korte, and Lov\u00e1sz). This paper notes that, in the case of the chordal graphs \\(G\\), the greedoid characteristic polynomial is given as an alternating sum \\((-1)^{|E|}\\sum (-1)^k a_k \\lambda^k\\), where \\(a_k\\) is the number of cliques of \\(G\\) having \\(k\\) vertices. It is shown that, for connected \\(G\\), the value of the ``\\(\\beta\\) invariant'' of the greedoid, defined as \\(|p^\\prime(1)|\\), is the number of blocks of the graph.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1868852$395DCA4A-D500-4290-B4ED-7816866FEA41","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1868852$74CD99CE-E677-4817-B21F-8057A852E5DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a06727f99c93aa58e84e3d476d4f6a1bed523458","datavalue":{"value":"05B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1868852$D71A86DA-B19F-415C-9F29-F65BFC17F84E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1efd9620bed5a656b1066e406d3d381c89ff11aa","datavalue":{"value":"1901901","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1868852$FD77F72D-2174-42F8-99D9-B8203E781D7D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dae41303426e6695786e3a6d28699919bfeab34a","datavalue":{"value":"chordal graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1868852$60F23712-24A9-4D14-91F2-32AC4A270924","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2a22a5f0c2b46f5f4796445f001af7e2048aa3dc","datavalue":{"value":"antimatroid","type":"string"},"datatype":"string"},"type":"statement","id":"Q1868852$1CECA6EA-9C0A-4FF5-9332-87E6A6A14AB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"605cb8d50a0cbbf8fdf20fa33f0562f05a8e4f67","datavalue":{"value":"greedoid characteristic polynomial","type":"string"},"datatype":"string"},"type":"statement","id":"Q1868852$B3050CED-5DEB-4C60-B59E-7C9EF696A694","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c1662b55279c3e33ec66388559459a3433b0a1cc","datavalue":{"value":{"entity-type":"item","numeric-id":590773,"id":"Q590773"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1868852$ECCFBC0F-0723-46DF-B5FB-C0FB63C26B2E","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":"Q1868852$0CA30FAD-5CA6-4896-B0C3-045691694F31","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f96fe31ad04408a28dcfd34fa43f2d2bdce8feda","datavalue":{"value":"https://doi.org/10.1016/s0012-365x(02)00500-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q1868852$08707439-4DDA-445C-B4FB-21E0C495032A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"afc24a10d9d2d4edd52e49fe0a90e29d25d3db9c","datavalue":{"value":"W2164196654","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1868852$23FEB3A6-17AD-44C3-B110-7912A9B06A68","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2b937ae0a93ebd9997a9842bdff5cf037e43979e","datavalue":{"value":{"entity-type":"item","numeric-id":4459341,"id":"Q4459341"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d56f61e37ca7deb01da9af70c4486424f7cf9bc1","datavalue":{"value":{"amount":"+0.9457257","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":"Q1868852$4099F215-0364-4357-ADD8-071ED5B2CCE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"91bbd986cc5759ec49d59d3c2183e8756f60565c","datavalue":{"value":{"entity-type":"item","numeric-id":3822188,"id":"Q3822188"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3dd19750588947d2d26fa063bc21e7fea609a015","datavalue":{"value":{"amount":"+0.94041157","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":"Q1868852$12847714-494E-49B9-A2E5-FDBDA362123B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"59fc586ff96eccfeeda7e6dfebe3140cd35b45c7","datavalue":{"value":{"entity-type":"item","numeric-id":4517020,"id":"Q4517020"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"06e3db7a430afc6205763551ce18568099f49bbd","datavalue":{"value":{"amount":"+0.9336456","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":"Q1868852$AE0938E6-9AE6-450B-A2AF-02A15C76D2D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"02f732603e155e5117e31e28f4b5d2bc89c129c3","datavalue":{"value":{"entity-type":"item","numeric-id":4033253,"id":"Q4033253"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dd676a57894aff728fba00c59b870f46b2db0faa","datavalue":{"value":{"amount":"+0.9286772","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":"Q1868852$D8CEFAE1-99FB-4A0D-9B67-604A5F9C4806","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"87cc6e95bc18a64c96d058bad067b5d5d95e0033","datavalue":{"value":{"entity-type":"item","numeric-id":6045410,"id":"Q6045410"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1df6b269ce27fad18e19eae2f099b221547a9d25","datavalue":{"value":{"amount":"+0.9278034","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":"Q1868852$F6C4C9B3-501E-43F2-981D-7F43906362F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5bd56f3127bf62873b1a32abf23124e91b3afd28","datavalue":{"value":{"entity-type":"item","numeric-id":832856,"id":"Q832856"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1df6b269ce27fad18e19eae2f099b221547a9d25","datavalue":{"value":{"amount":"+0.9278034","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":"Q1868852$2DF9458B-EF78-44F4-8E65-2D6DD05E485E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"970c9dde1dfe6807c9aae340847a1865e15eecb8","datavalue":{"value":{"entity-type":"item","numeric-id":1109781,"id":"Q1109781"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"26a21b354a5f6d1191da88df7af644bbad528be0","datavalue":{"value":{"amount":"+0.9246193","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":"Q1868852$409A36C4-1C3F-4DA5-8B9E-700E8F76D602","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7dcbf4d7141f675cc7206bc9cd3fc219ec836313","datavalue":{"value":{"entity-type":"item","numeric-id":624543,"id":"Q624543"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d51dc86553bbfd7b8398e67190fbc099ec3b5f2d","datavalue":{"value":{"amount":"+0.9221556","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":"Q1868852$5614FC56-FEF7-472B-BFEA-84333D537BD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4ca7f2ee9a983c521d4907499b9cd70aceed8b74","datavalue":{"value":{"entity-type":"item","numeric-id":3328563,"id":"Q3328563"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"94fcca7f2eda3e3f4ab328df43b21bc1c0018002","datavalue":{"value":{"amount":"+0.9210576","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":"Q1868852$9F051130-45D9-4489-93BD-787A18DB6290","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"59ff62a63929e4c6b8d4c7bf058f39d9880db8c5","datavalue":{"value":{"entity-type":"item","numeric-id":4693359,"id":"Q4693359"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"93034db8c89460aed07feba0e3d44860e1265b3d","datavalue":{"value":{"amount":"+0.92072445","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":"Q1868852$97867AB9-6290-4560-BF7F-AD13EAFDABB9","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Chordal graphs and the characteristic polynomial","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Chordal_graphs_and_the_characteristic_polynomial"}}}}}