{"entities":{"Q406698":{"pageid":408465,"ns":120,"title":"Item:Q406698","lastrevid":61618296,"modified":"2026-04-11T00:31:04Z","type":"item","id":"Q406698","labels":{"en":{"language":"en","value":"Note on the subgraph component polynomial"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6341628"}},"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":"Q406698$8E286600-E9FC-4BF8-9FCA-264B759C604C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ac522cc9ce94952082d2e5893c42f0699722d2db","datavalue":{"value":{"text":"Note on the subgraph component polynomial","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q406698$1842678A-7FA0-4AAF-9509-A9DAD197C817","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1380866733b6e977a48c1bb2448f3d98cd0e655f","datavalue":{"value":"1298.05168","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q406698$18DB2F52-1A11-4F33-AF1B-9783DE8A12A0","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0427178b677b20f1cbc5d2422e589328b4277e22","datavalue":{"value":{"entity-type":"item","numeric-id":406697,"id":"Q406697"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q406698$F325BC67-C6D8-4620-805A-99AF1CA9DD73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3a8e66acb3f891aceaa7047e20525c5d6c34f215","datavalue":{"value":{"entity-type":"item","numeric-id":389615,"id":"Q389615"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q406698$4BB8B190-EFFF-4C00-A30D-7A0F5659CE79","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":"Q406698$4F3A2944-15F7-4CCB-86F0-8E0A28CB19A2","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d460cc5018b7d6687b87ccaaf2ba1aff43b53078","datavalue":{"value":{"time":"+2014-09-09T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q406698$3602F8D1-FEE5-48EC-A3C1-2ABF320D74AC","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"243ffe3cecd2e529c2b660aba20f918ba8ac901c","datavalue":{"value":"https://arxiv.org/abs/1311.6856","type":"string"},"datatype":"url"},"type":"statement","id":"Q406698$D7E5B819-4297-4526-9F21-36D5B2E63FBF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"f0ef51239b74f5013e64dba80e3dca102b2451ee","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i3p27","type":"string"},"datatype":"url"},"type":"statement","id":"Q406698$15F3413B-4724-42D8-9E0E-AEE7F40BE7D1","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"98addde0d488543e1a4ab1bbb5c027beb33a95a7","datavalue":{"value":"Summary: \\textit{P. Tittmann} et al. [Eur. J. Comb. 32, No. 7, 954--974 (2011; Zbl 1229.05124)] introduced the subgraph component polynomial \\(Q(G;x,y)\\) of a graph \\(G\\), which counts the number of connected components in vertex induced subgraphs. This polynomial encodes a large amount of combinatorial information about the underlying graph, such as the order, the size, and the independence number. We show that several other graph invariants, such as the connectivity and the number of cycles of length four in a regular bipartite graph are also determined by the subgraph component polynomial. Then, we prove that several well-known families of graphs are determined by the polynomial \\(Q(G;x,y)\\). Moreover, we study the distinguishing power and find simple graphs which are not distinguished by the subgraph component polynomial but distinguished by the characteristic polynomial, the matching polynomial and the Tutte polynomial. These are partial answers to three open problems proposed by Tittmann et al. [loc. cit.].","type":"string"},"datatype":"string"},"type":"statement","id":"Q406698$4E22EC53-8F2C-40B9-AD56-6A8BFD4E5415","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"26ba4f06ff5c7e92bd3a85f32aa625ae214ffe0f","datavalue":{"value":"05C31","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q406698$31CFB215-5F1A-40A3-BE00-A80FE3A757BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1de0493fc6f7fe4361a54e7c2f5546e4ec52adf0","datavalue":{"value":"05C30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q406698$9D066015-3E42-4C45-A648-4715602F0DF1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"0556c939d5f80905b689a8f78ecccbf9dd8e2697","datavalue":{"value":"05C82","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q406698$5101B3AC-7139-484F-B62A-595CD43C8919","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f3c0e7b2db18c1fb814b7081b37d324067c3db39","datavalue":{"value":"6341628","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q406698$311AABFA-B5E7-4077-8E3B-94D6A2BFDE84","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c4c58746c65b498a296790abd170bc3398210afd","datavalue":{"value":"graph polynomial","type":"string"},"datatype":"string"},"type":"statement","id":"Q406698$A0C8D9AD-4F2B-4418-B65C-2ECDC581BA59","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":"Q406698$02C760DD-E0A0-456E-BF92-1524A3D86175","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f1e0780ef9fc13205a998c28c82fa2b8e9d6af5a","datavalue":{"value":{"entity-type":"item","numeric-id":709243,"id":"Q709243"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q406698$51127CC7-80AA-4A16-955A-24DF950D3E30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6d6cfc313dc74b127a55e7d48c0fc7dafd0adbab","datavalue":{"value":{"entity-type":"item","numeric-id":967288,"id":"Q967288"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q406698$FC4341A0-24FB-4F8F-A8DE-2F18B2865BA1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"00f29c21a193b32b6a4f88c50e19bafb9a324634","datavalue":{"value":{"entity-type":"item","numeric-id":1041177,"id":"Q1041177"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q406698$D2424FF6-9810-45C6-80EC-00E2B3D2A90F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e7d3b9ea4191d0e8f38b85f31489e94d8e2e8043","datavalue":{"value":{"entity-type":"item","numeric-id":1010839,"id":"Q1010839"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q406698$50DA33CF-124F-46A1-9164-8D18314B9A26","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6007235c376c67acd355ca771e5554344415d7a0","datavalue":{"value":{"entity-type":"item","numeric-id":730958,"id":"Q730958"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q406698$9C9923DF-C8AB-4C3F-AF64-EE7EB61A719E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"41ab95cfd69e10430c9e72fb53fae7f5a4250a3f","datavalue":{"value":{"entity-type":"item","numeric-id":4947393,"id":"Q4947393"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q406698$8F0393AF-BDBA-419D-B95D-9D29BAB682B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3fba5761bf4006098325fb2a92d8aee4e5689f3a","datavalue":{"value":{"entity-type":"item","numeric-id":409433,"id":"Q409433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q406698$ED4FD19F-261E-44AB-9F67-AD07749DA05C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"be5e57b2844a5da9ed0526d7a5aadde88ea0780e","datavalue":{"value":{"entity-type":"item","numeric-id":3064401,"id":"Q3064401"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q406698$437D9EC6-CDED-457A-B0D0-6DC40BEABE1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"659997da610712b4fa3240ed68fa39118651c662","datavalue":{"value":{"entity-type":"item","numeric-id":1229232,"id":"Q1229232"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q406698$FC2C3FA6-F161-4DD4-9158-B5CFF3C32C5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8afaf227be465e13a82520fa2837be488bb2cf79","datavalue":{"value":{"entity-type":"item","numeric-id":648964,"id":"Q648964"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q406698$EE717390-C499-49F7-AC3C-3E268FF37763","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d56111fbbc24e473005153a4773012eb6e64d00c","datavalue":{"value":{"entity-type":"item","numeric-id":5420030,"id":"Q5420030"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q406698$E678C077-558F-43EC-88F1-6F9D0593F579","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0b342389349da4779bdd7906e3beda3158c71d6a","datavalue":{"value":{"entity-type":"item","numeric-id":975503,"id":"Q975503"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q406698$B3BFD90B-B3BF-4EA7-922D-E91A34284679","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c2c594e9705e780a6a4b2b01479e5d5553e79570","datavalue":{"value":{"entity-type":"item","numeric-id":5572939,"id":"Q5572939"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q406698$22B9AF0F-1758-4691-B352-9DD369FB2003","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eb824f69c8efd3ad7aef3678db7c1893ee015b65","datavalue":{"value":{"entity-type":"item","numeric-id":1102985,"id":"Q1102985"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q406698$0E66C9B3-F57E-4513-B622-2430183CCBCD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"27afb7aceceea7740fc3507b1fc90e04036f35d2","datavalue":{"value":{"entity-type":"item","numeric-id":456395,"id":"Q456395"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q406698$DD737E40-2158-4F4E-A3E1-F70BDEF04140","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4e1e7f80942b85685dcb0923df3cd04d90e74bf8","datavalue":{"value":{"entity-type":"item","numeric-id":1889848,"id":"Q1889848"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q406698$DD837316-E0BB-4474-851E-5012EFA4B5B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c121e2913075365aedcf3d0f58cd0e173a469462","datavalue":{"value":{"entity-type":"item","numeric-id":1885023,"id":"Q1885023"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q406698$B0944B7C-EA6C-4AFA-B377-29C4D98F5A33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6c025ec80459931f899d1946429af83bd4521c24","datavalue":{"value":{"entity-type":"item","numeric-id":5560915,"id":"Q5560915"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q406698$9062137F-943F-4622-86F6-2EE86E876C8A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4e7ff2d22bc7d078dbd116972264bd667e76d2d7","datavalue":{"value":{"entity-type":"item","numeric-id":648958,"id":"Q648958"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q406698$970B068C-047A-483D-B5C9-814082CF0466","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6a8fc8da6e97b9d0bad2c652987e500d1f7eac1c","datavalue":{"value":{"entity-type":"item","numeric-id":426819,"id":"Q426819"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q406698$C1BB701F-D52A-460D-8EC0-5747B363D0CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"36198b1d211977d66a47c2610d629e8fba07f517","datavalue":{"value":{"entity-type":"item","numeric-id":5826302,"id":"Q5826302"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q406698$A6F678DA-CE9D-4954-BF02-F4D978BEAC33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"82f4a06beed8b92ce004208dcc0795d0f1f952f0","datavalue":{"value":{"entity-type":"item","numeric-id":710585,"id":"Q710585"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q406698$4BDA108F-6B47-4434-B1F0-DE1987BE3539","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"89db9226c2b83f23e033f884caa306cdee537381","datavalue":{"value":{"entity-type":"item","numeric-id":4831409,"id":"Q4831409"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q406698$4F3D2E7D-9363-4D08-9F0A-F1E997C5F3D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"65ec57fc36372a9979d51de5eb08874222961729","datavalue":{"value":{"entity-type":"item","numeric-id":1003776,"id":"Q1003776"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q406698$316DAF14-C628-4C72-8F8E-6EEBD50CDA8C","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"8e2a4c452360aeff9d462b7cdf0f46a1d3cfb5fa","datavalue":{"value":"bafkreieaicfu72hq2mrr424dfysabaccsytctt7p7mou5fvhfpgz3ohsgq","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q406698$6E1BC1C8-ABA7-426E-9EF9-5DC22AD7E5CC","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f799598ba31368539923054ecb2b879408aa1302","datavalue":{"value":{"entity-type":"item","numeric-id":4568191,"id":"Q4568191"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0014cd6ea90fa3d77f928d32c4ec54290919ee42","datavalue":{"value":{"amount":"+0.8068019151687622","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":"Q406698$DA4460B0-1EED-43C8-9D83-3DB145834168","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"05d8791359433ebebce8a345e0b801dfb21e38e8","datavalue":{"value":{"entity-type":"item","numeric-id":1304820,"id":"Q1304820"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3800182855588c5f027eaf304d9912fabbd4cdf2","datavalue":{"value":{"amount":"+0.8025110363960266","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":"Q406698$FCEFE2E7-6E36-47DD-99EA-914E4B08CE5C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4a2a139cde6ff8c2de3f0811d3432f8717b19c8c","datavalue":{"value":{"entity-type":"item","numeric-id":1885023,"id":"Q1885023"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bdfed7001af6ffc00d511744cd48ba88117d6d34","datavalue":{"value":{"amount":"+0.7839438319206238","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":"Q406698$469C2D3F-F953-40F3-8977-54B148C0B03B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d3407115832e4fdc79821b5b7bc0c8ec83f284c8","datavalue":{"value":{"entity-type":"item","numeric-id":4910454,"id":"Q4910454"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ac34096065571b3a85cd92abd1b445d9f17affd7","datavalue":{"value":{"amount":"+0.7795361280441284","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":"Q406698$3EB97B4C-501B-41CF-B32F-65557B825BBF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e221ab73429c3ab78c06faf84071ccdbf6669fe9","datavalue":{"value":{"entity-type":"item","numeric-id":648958,"id":"Q648958"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b3e7d0b13d33753806b35da0ceb746a0dca72872","datavalue":{"value":{"amount":"+0.7579001188278198","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":"Q406698$550D4C34-0321-4435-828B-976FA9D1D8E0","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Note on the subgraph component polynomial","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Note_on_the_subgraph_component_polynomial"}}}}}