{"entities":{"Q1106856":{"pageid":1117605,"ns":120,"title":"Item:Q1106856","lastrevid":69654966,"modified":"2026-04-13T08:29:40Z","type":"item","id":"Q1106856","labels":{"en":{"language":"en","value":"The number of maximal independent sets in a connected graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4063120"}},"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":"Q1106856$9AEDEA9F-6FB2-41C3-979C-1104B619552B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d39650ba40ced2a2f40b37d84cc4a2077ad2c02d","datavalue":{"value":{"text":"The number of maximal independent sets in a connected graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1106856$1450E1FD-3726-474C-8B10-038C445C601A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"397e3cdef29a572f97fb4829c87453a3bf18f6c4","datavalue":{"value":"0652.05027","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1106856$32B9E4DD-9326-4E9C-B960-A573F4E12B3D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"bf2fd5f6e8a005faebb8e937787bb0e5be44c334","datavalue":{"value":"10.1016/0012-365X(88)90114-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1106856$DAC01E15-2BD1-4613-985C-1C9687F06333","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"7eea8e7d77c3bd85961dad34f48622f9613bb045","datavalue":{"value":{"entity-type":"item","numeric-id":594100,"id":"Q594100"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106856$935CD87F-79E9-45C1-9C8C-0549CDAEE7DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"869dab8b43689dfc97a92e2a50b736bbf844e44e","datavalue":{"value":{"entity-type":"item","numeric-id":796545,"id":"Q796545"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106856$3EC29FCE-6F5A-4155-A9A0-6033D0CE2F5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"5094919efa29cd73eefffd7ee0301568f780f61b","datavalue":{"value":{"entity-type":"item","numeric-id":800917,"id":"Q800917"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106856$216D9F44-F97A-409D-B8D2-A4BE42E1F0BF","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":"Q1106856$D4E1B775-BFD8-4E45-A704-582C380C63BA","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1106856$F0DEB8CC-A223-4D5D-A420-641FB2F9BA06","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"87e1a52faf655883f83169852255971b02f848f3","datavalue":{"value":"Let \\(g(n)\\) be the maximum number of maximal independent sets, which a connected graph on \\(n\\) vertices can have. It is proved that  \\[  g(n) = \\begin{cases} 2.3^{n/3-1} + 2^{n/3-1} \\quad&\\text{if }n\\equiv 0\\pmod3 \\\\ 3^{[n/3]} + 2^{[n/3]-1} \\quad&\\text{if }n\\equiv 1\\pmod3 \\\\ 4.3^{[n/3]-1} + 3.2^{[n/3]-2} \\quad&\\text{if }n\\equiv 2\\pmod3. \\end{cases}  \\]  All connected graphs with \\(g(n)\\) maximal independent sets are the following (Theorem 3): \\(n\\leq 4:\\) the complete graphs \\(K_ n\\); \\(n=5:\\) The cycle \\(C_5\\), the complete graph \\(K_5\\) and the graphs shown in Fig. 1; \\(n\\geq 6:\\) the graphs \\(E_ n\\) shown in Fig. 2, where the subgraphs \\(G_ 1\\), \\(G_ 2\\) are both the triangles or both the complete graphs \\(K_ 4\\) or \\(G_ 1\\) is the complete graph \\(K_ 4\\) and \\(G_ 2\\) is the triangle.   {Remark: The two figures may be looked at in the printed version of Zentralblatt f\u00fcr Mathematik.}","type":"string"},"datatype":"string"},"type":"statement","id":"Q1106856$92DF8647-FB01-4837-894E-3E1596259426","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"ebe4d44a08a58073803722e37fc039de15c45af0","datavalue":{"value":{"entity-type":"item","numeric-id":761465,"id":"Q761465"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106856$FBFA30DE-599C-4AD5-BA2B-AB4518FF3441","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1106856$ABD27F3C-5388-4A32-B2E7-36B3A9A19443","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f59108a3edd49be898c5e5da5ca7c584a6ce9305","datavalue":{"value":"4063120","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1106856$3A74D6CC-D483-40E4-B5B6-6DCA2E81EC36","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6c370b066aeb6aec88cc0130aa61a206a94b671f","datavalue":{"value":"central cutpoint","type":"string"},"datatype":"string"},"type":"statement","id":"Q1106856$CA9FC691-9080-46B1-8674-CF9565A7C507","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6dfd13b3fcafee84529913335756c3088d4e1f6c","datavalue":{"value":"block","type":"string"},"datatype":"string"},"type":"statement","id":"Q1106856$CA8B21F9-65C0-45F7-AB00-35D09495EFF7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a0d9db75be08c043165f35050eaec69bbe0078be","datavalue":{"value":"cutpoint graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1106856$A5AD7EF4-FCEC-4F0C-A6CF-5AAD2540F4A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0cc3070e50d573106bcff9e7a9af31b4e37f89dc","datavalue":{"value":"pendant block","type":"string"},"datatype":"string"},"type":"statement","id":"Q1106856$D1005A2F-FD56-487D-B31E-8817ACDE5B04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"31ce2647f4f18782d629175670cb38f40b07cbb9","datavalue":{"value":"penultimate vertex","type":"string"},"datatype":"string"},"type":"statement","id":"Q1106856$F3A32498-86A4-4DC1-A0AD-100B1C5A8A13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"79aef9db8e0c683ce6cc529a2f7d1366a38210b6","datavalue":{"value":"block graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1106856$46F55A9B-B9DA-48D2-8AE0-B7E7F12015AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1c14033d0eb507190bce6635e40fd50c25ec9adc","datavalue":{"value":"maximal independent sets","type":"string"},"datatype":"string"},"type":"statement","id":"Q1106856$E1F81D6D-CC40-42C0-873A-6D7F3E5D7E0F","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":"Q1106856$77E29063-A58F-4DAC-9994-BA02F8D5BA9F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"751bb518407806a0775e238de3cb997abdfa1f23","datavalue":{"value":{"entity-type":"item","numeric-id":1324287,"id":"Q1324287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106856$35BA9BAA-D489-48D1-8DD6-4BE56994995B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"65c334f24f0ea0f5930a0f10f3816e5cbac17eea","datavalue":{"value":{"entity-type":"item","numeric-id":5920767,"id":"Q5920767"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106856$A03B18F5-4BE3-4D95-8CD9-866319CA4D06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c07e79386d05b178c2d77aaa3d02447ec0feea2b","datavalue":{"value":{"entity-type":"item","numeric-id":3789596,"id":"Q3789596"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106856$6A3A4E1F-E06C-40A2-954C-B9389ADC82C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"66dea37f00b4a8b5a15685a25911c290a2c67fbf","datavalue":{"value":{"entity-type":"item","numeric-id":3708817,"id":"Q3708817"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106856$C647DF9A-F0CB-4639-9685-807DE24EA658","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c06ecc832df64e35111dc04fbe4203aa130cf2c9","datavalue":{"value":{"entity-type":"item","numeric-id":3791174,"id":"Q3791174"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4b62ad271a384048fc5c6f47940a616e40bf3eea","datavalue":{"value":{"amount":"+0.8767151832580566","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":"Q1106856$8B812730-88D2-4D8D-B0A6-7ACC8D7F865B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fb5578ce28a9e8952157080712af8ecf146db18d","datavalue":{"value":{"entity-type":"item","numeric-id":1292823,"id":"Q1292823"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"633491f317bb6f06a9ffd775d107b021b5ee6e15","datavalue":{"value":{"amount":"+0.862854540348053","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":"Q1106856$3CA5643F-D2E3-40D2-88B9-FF93BC48E409","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"930b281b257531313a147b1be45c9b77d7430f23","datavalue":{"value":{"entity-type":"item","numeric-id":6055407,"id":"Q6055407"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a454618ea43a98af42c81aa11329db11d39fb040","datavalue":{"value":{"amount":"+0.8486748337745667","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":"Q1106856$B952D283-4AEF-4E02-B97E-CABE42D01C92","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cc834e0c826fb1e939f100dc4f2912758f590d3d","datavalue":{"value":{"entity-type":"item","numeric-id":3105531,"id":"Q3105531"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"64b4e22dd1520c8853f349e83e74f221837ecb61","datavalue":{"value":{"amount":"+0.8409236669540405","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":"Q1106856$5ABBFEE5-471E-46BC-BECD-7139DA0EAB83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"96705620f52a5a6f2c46c2a7f4e5943090e5a3d9","datavalue":{"value":{"entity-type":"item","numeric-id":1928530,"id":"Q1928530"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0fb2aafb7d4401df05aec1495e1ad2ffd2a36900","datavalue":{"value":{"amount":"+0.8313186168670654","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":"Q1106856$B0206767-0152-4E5E-8CC6-5EC152B94E54","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The number of maximal independent sets in a connected graph","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_number_of_maximal_independent_sets_in_a_connected_graph"}}}}}