{"entities":{"Q405176":{"pageid":406943,"ns":120,"title":"Item:Q405176","lastrevid":61642320,"modified":"2026-04-11T00:40:00Z","type":"item","id":"Q405176","labels":{"en":{"language":"en","value":"Certificates for properties of stability polynomials of graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6340164"}},"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":"Q405176$681CB15C-6051-44A3-B833-D30E9392FC42","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1f3eb8f4a98fc6df111576ee1ccf3cc928cc19e7","datavalue":{"value":{"text":"Certificates for properties of stability polynomials of graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q405176$1779C707-D99A-4D81-A7A2-47408DA154ED","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4781b5d8e60484ce6035f3bc61d8f057bdbb5491","datavalue":{"value":"1300.05137","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q405176$7733D6A6-9989-4B95-99AA-0B8669E98FFA","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6dbf34036d57dcaef390a5d5b1c5b97df08a687a","datavalue":{"value":{"entity-type":"item","numeric-id":405173,"id":"Q405173"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405176$85EF4F83-9E5F-483F-85E2-9381AF2B204B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7033e1540cad85d9c7a57e9538ddce0901452aa5","datavalue":{"value":{"entity-type":"item","numeric-id":405175,"id":"Q405175"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405176$27CAAA33-7EC2-4019-A847-8A08FFBB3561","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c10b05f408b175fc9b864bccc0f940febdbc4691","datavalue":{"value":{"entity-type":"item","numeric-id":810039,"id":"Q810039"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405176$BA1641D1-640F-4CC0-A6A9-01AA678B2E16","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":"Q405176$B77DCE19-BE3B-4670-AFC8-A093145E9970","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f9d8fea32a46af1bd8128cc5dcfc32073a3817d0","datavalue":{"value":{"time":"+2014-09-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q405176$AFA4C2FD-CF76-4772-ADCB-1691C1B20166","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"5c709685c3377125ceafa6ab22138cc6af911a3e","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i1p67","type":"string"},"datatype":"url"},"type":"statement","id":"Q405176$168D9876-C93C-41D3-9F44-58B2697B2B7A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"02c86d411f7a6fea54474faa6c53e091eb40d72f","datavalue":{"value":"Summary: A stable (or independent) set is a set of vertices where no two of the vertices in the set are adjacent. The stability polynomial \\(A(G; p)\\) of a graph \\(G\\) is the probability that a set of randomly chosen vertices is stable where the probability of each vertex being chosen is \\(p\\), with choices independent. This polynomial is analogous to the chromatic polynomial in a precise sense. This paper considers factorisation of stability polynomials, following work by Morgan and Farr on factorisation of the chromatic polynomial. The stability polynomial \\(A(G;p)\\) is said to have an s-factorisation with s-factors \\(H_{1}\\) and \\(H_{2}\\) if \\(A(G; p) = A(H_{1};p) A(H_{2};p)\\). This clearly occurs when \\(G\\) is a disjoint union of \\(H_{1}\\) and \\(H_{2}\\). We find many other cases where such factorisation occurs even when \\(G\\) is connected.    We find 152 different s-factorisations of connected graphs of order at most 9, and two infinite families. We introduce certificates of s-factorisation to explain s-factorisations in terms of the structure of \\(G\\). Short certificates for s-factorisations of connected graphs of order at most 6 are found. Upper bounds for the lengths of the certificates of s-factorisations are given. We also use certificates to explain \\textit{stability equivalence}, when two graphs have the same stability polynomial. We give certifications of stability equivalence for two infinite families of graphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q405176$D8F64478-A691-47AB-A9BD-E50DEF571253","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"26ba4f06ff5c7e92bd3a85f32aa625ae214ffe0f","datavalue":{"value":"05C31","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q405176$FC633FB6-373C-4805-8FDD-C283931CD52A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q405176$5FDAA67F-9085-4742-ABCB-1DF960719B61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q405176$71A71222-F1F9-4182-B4D0-84D245A8BFCC","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"24e07047810c56c8f586d0ae0b542668401c391c","datavalue":{"value":"6340164","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q405176$89774703-61FE-408C-8316-A7D6C657BA0E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cfa746c65c23fb4103c18d85c3fa09499263d5b4","datavalue":{"value":"stability polynomial","type":"string"},"datatype":"string"},"type":"statement","id":"Q405176$6A1A46A7-2B97-422B-9B07-0FE7950E914C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"50940ff582f152d511fd3e73cca71bead0f1bf00","datavalue":{"value":"chromatic polynomial","type":"string"},"datatype":"string"},"type":"statement","id":"Q405176$ED19B203-BFA1-4226-A2BD-6988A9EDFAE6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1f42ab1ef68844a89c8a5f8b94dfe3e5110dda50","datavalue":{"value":"certificate","type":"string"},"datatype":"string"},"type":"statement","id":"Q405176$56BC20B7-54C5-4676-8509-C0EA2ACC4F62","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b20e79d688a43c3daf2958f08e6ec6b89eb06b15","datavalue":{"value":"stability equivalence","type":"string"},"datatype":"string"},"type":"statement","id":"Q405176$2361D4CF-71A3-410C-9EBD-B62CCF74203F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e43300c5538e3976a9e4802ab561875bf860e181","datavalue":{"value":"s-factorisation","type":"string"},"datatype":"string"},"type":"statement","id":"Q405176$45A6B770-71DC-413A-984A-2502FEC67E31","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":"Q405176$15B156EB-08C8-4DF7-9EBC-387AFED762EF","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"28a6c07a52b83cfbba34f0cc37fdc712e2be17b3","datavalue":{"value":{"entity-type":"item","numeric-id":5377353,"id":"Q5377353"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405176$F48C7DD2-EE3B-440D-85AA-9B1B25FD1ADA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0d6db223a21c5eebe0b4316752d1d043e9243033","datavalue":{"value":{"entity-type":"item","numeric-id":810040,"id":"Q810040"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405176$E4C59C3C-ED71-4290-B0D8-C927B3043B6B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ed5cb6627425980d25b7b37da2abfdd0b9b38a06","datavalue":{"value":{"entity-type":"item","numeric-id":3043192,"id":"Q3043192"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405176$755B6A3E-F768-4D99-BE1C-98536D9F0091","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cff90b53746deaf40f0bd975035788d645dc76ab","datavalue":{"value":{"entity-type":"item","numeric-id":5682013,"id":"Q5682013"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405176$AC1E2DF1-C6B7-40A6-B761-227074B56682","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"99d7a3ca62017ccf7e1fb50a5b4f33f6a3bac6e3","datavalue":{"value":{"entity-type":"item","numeric-id":4053708,"id":"Q4053708"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405176$7B954EFF-C8D4-4874-9B35-4188CDE2EB58","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"12b08264f8870a70a11a22ef30fad6a5143fb320","datavalue":{"value":{"entity-type":"item","numeric-id":659723,"id":"Q659723"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405176$721B9EFF-F293-4907-AEE3-253A6F587C9E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bdfcb8b22a2544d3e59f80501c7073d0f56301dd","datavalue":{"value":{"entity-type":"item","numeric-id":2380230,"id":"Q2380230"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405176$CA2BFCC9-91F1-4917-A1B2-AEA9B119D885","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6991bdd2e4771b46f2fddf6f8a750a7c045ce215","datavalue":{"value":{"entity-type":"item","numeric-id":2380229,"id":"Q2380229"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405176$01102BEF-30D9-479A-A7B4-878342F798E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0d3ec63f225852ceb4937bb2fd18dad07edf76e0","datavalue":{"value":{"entity-type":"item","numeric-id":409454,"id":"Q409454"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405176$F3B0E385-BBA2-4543-ABB6-69D26643E80C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4acf4c3ebdda48c50753181221858f1dc6190e96","datavalue":{"value":{"entity-type":"item","numeric-id":968175,"id":"Q968175"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405176$0F378F24-1EF8-499D-A05B-005C413A7C1D","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"a2474628205170f2d3fa2dc96edff0cd5078323d","datavalue":{"value":"bafkreidz372mqdfyu4czcnicxkjuweejgoxw3f6o62c2w3lb2kzgur6jk4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q405176$3AF5FA43-13C3-45D0-85EC-BDD858C04582","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2298267bcf523e4d506b797f8a49742d747d95d0","datavalue":{"value":{"entity-type":"item","numeric-id":2380229,"id":"Q2380229"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fe89528dfe7797f24852f19666d8228954157077","datavalue":{"value":{"amount":"+0.778986394405365","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":"Q405176$9C3EA357-0301-48A6-B580-D867645C0BEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"97de43371356ce58d85fb39c84cfe240b900504e","datavalue":{"value":{"entity-type":"item","numeric-id":1753011,"id":"Q1753011"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c8010e48bea2129bc9f3646154ef7a051a73cb44","datavalue":{"value":{"amount":"+0.7717999815940857","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":"Q405176$AAADF783-D505-4A9B-A3FC-157D697229A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fd481d1ff6f03dfe6445ebfea4bafc362f36bce0","datavalue":{"value":{"entity-type":"item","numeric-id":2380230,"id":"Q2380230"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4189f6410e0bfeeec4b979a43f2972987d998a9c","datavalue":{"value":{"amount":"+0.7443731427192688","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":"Q405176$A6798D21-94FE-43AD-B766-AC8E6D6A5EB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0423b50e2826c75a5f6c5bdc4823f8bb91f627e9","datavalue":{"value":{"entity-type":"item","numeric-id":5377353,"id":"Q5377353"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fbe58f506b94fa7fbbe879b27e2764c1852a627b","datavalue":{"value":{"amount":"+0.7408992052078247","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":"Q405176$DFC21EBF-EEA8-452B-ACF2-CBE13F078401","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"740485ea739381aeda6179f946eb1b1a6db78359","datavalue":{"value":{"entity-type":"item","numeric-id":409454,"id":"Q409454"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0a6045eb68342f6c4368a819689c5b5a341c6076","datavalue":{"value":{"amount":"+0.7244899272918701","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":"Q405176$46AEE5F1-EA8B-40BD-AE57-BCBC91FFA3E7","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Certificates for properties of stability polynomials of graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Certificates_for_properties_of_stability_polynomials_of_graphs"}}}}}