{"entities":{"Q1204485":{"pageid":1215234,"ns":120,"title":"Item:Q1204485","lastrevid":66348150,"modified":"2026-04-12T09:30:13Z","type":"item","id":"Q1204485","labels":{"en":{"language":"en","value":"A characterization of well covered graphs of girth 5 or greater"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 130578"}},"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":"Q1204485$6F6AF3A0-8B46-4B28-974A-0D5B92D425C4","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b68024a92232b57a4f6c26d8ebdf508ba213b8dc","datavalue":{"value":{"text":"A characterization of well covered graphs of girth 5 or greater","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1204485$586AB04A-8836-48CA-B90E-A59B03596CA7","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0c65a8a96745d73cb9de3c13fe999571fb58f1d6","datavalue":{"value":"0777.05088","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1204485$ACF67573-E78C-46B8-9F8F-9669EC91CEB6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1c28117db9c7e125c64a62279c5126736944bfba","datavalue":{"value":{"entity-type":"item","numeric-id":323040,"id":"Q323040"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1204485$7BD6952A-E58D-4E50-8E7B-5D0056E214FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b456e163893e6e87b237f13f92631ec6792af82d","datavalue":{"value":{"entity-type":"item","numeric-id":323039,"id":"Q323039"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1204485$E70FDF90-77C0-41F2-85B0-2BE704FCC00D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"5676fa5282611dbd0fab8edb7a4f82cf8ae7a025","datavalue":{"value":{"entity-type":"item","numeric-id":215016,"id":"Q215016"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1204485$AF64D6EA-9280-4C53-ABB0-7D48C97DEBB0","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f07f6fd6d97bd24ff86249abf8a501d3b63b437d","datavalue":{"value":{"entity-type":"item","numeric-id":256978,"id":"Q256978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1204485$B7D38928-5EF7-4B5B-9989-691498799984","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"fd1a91bacb3b86e97f56b6757c45d39c4521bbf1","datavalue":{"value":{"time":"+1993-03-10T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1204485$34C8D3A4-1A6E-4ABE-80FB-C4172D9CF552","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b0147192895933ba943656121dbd2e9b4e3d7837","datavalue":{"value":"A graph is well covered if every maximal independent set has the same number of vertices. A vertex \\(x\\), in a well covered graph \\(G\\), is extendable if \\(G_ x=G-\\{x\\}\\) is well covered and the maximal independent sets of \\(G\\) and \\(G_ x\\) have the same cardinality.   In 1983, \\textit{A. S. Finbow} and \\textit{B. L. Hartnell} proved: Let \\(G\\) be a graph of girth \\(\\geq 8\\). \\(G\\) is well covered iff its pendant edges constitute a perfect matching [Ars. Comb. 16-A, 189-198 (1983; Zbl 0559.90095)].   The main result of this paper is the following: Let \\(G\\) be a connected, well covered graph of girth \\(\\geq 5\\). Then either   (a) \\(G\\) contains an extendable vertex; this is equivalent with the condition that the vertex set of \\(G\\) can be partitioned into two subsets, the first of which contains the vertices of disjoint pendant edges of \\(G\\) (there are any other pendant edges in \\(G)\\) and the second subset contains the vertices of those disjoint 5-cycles which are without adjacent vertices of degree \\(\\geq 3\\) (Theorem 2), or   (b) \\(G\\) is isomorphic to one of the siz graphs: \\(K_ 1\\), \\(C_ 7\\) (i.e. 7-cycle 123...7), graph \\(P_{10}\\) (i.e. 10-cycle 123...10 with 2 additional ``diagonal'' edges 1-5 and 2-8), graph \\(P_{13}\\) (i.e. 13- cycle 123...13 with 4 additional ``diagonal'' edges 1-8, 2-6, 5-12, 7- 11), graph \\(Q_{13}\\) (i.e. 13-cycle 123...13 with 5 additional ``diagonal'' edges 1-5, 1-10, 2-8, 4-11, 7-11) or graph \\(P_{14}\\) (i.e. a graph of Petersen's type consisting of 7 edges \\(1-1'\\), \\(2-2',\\dots,7- 7'\\) and two 7-cycles 123...7 and \\(1'3'5'7'2'4'6')\\) (Theorem 3).   The authors described the graphs \\(P_{10}\\), \\(P_{13}\\), \\(Q_{13}\\), \\(P_{14}\\) using more visual figures.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1204485$15AB7012-5D1D-4EA2-81FB-25B2135B2D33","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":"Q1204485$7E03D0E0-6D4D-4430-9753-53480EF4EBC2","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1204485$0B120F86-105F-4733-8315-DCA50B19AD80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1204485$BEB4950C-22E0-4674-A0FB-C2969F6B449C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"bc74d58b5da89c40758964cb6a48d1bfcf2ef501","datavalue":{"value":"130578","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1204485$FEF07E9D-C2F5-40BA-B405-7CF83701E3D2","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7ae5cad662cee9457a0e88de5ca640ccabb9ba00","datavalue":{"value":"maximal independent set","type":"string"},"datatype":"string"},"type":"statement","id":"Q1204485$293461CD-A8CE-4905-B124-CCCD6E4E4887","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"64f82f1fa44704f17b715e01811ed0642b0b2cf5","datavalue":{"value":"well covered graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1204485$19E9A6B1-3DC5-44B9-B367-5427A5D286A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a1a173748f93e4f70aa784451677e2ec88ea88e5","datavalue":{"value":"girth","type":"string"},"datatype":"string"},"type":"statement","id":"Q1204485$0A0E6EE0-0533-439C-892B-7E9F0B657B78","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"19ec132a1ede33f50fb04fa222303f9cda249a50","datavalue":{"value":"perfect matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q1204485$947E5D8B-B3F8-4F94-86B2-C4537107F574","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fbb63ada421465f6628a11d2fd71d96f79f776ce","datavalue":{"value":"extendable vertex","type":"string"},"datatype":"string"},"type":"statement","id":"Q1204485$7247C4CB-9657-42FE-BE13-C2CF005391BD","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":"Q1204485$DA4AD829-B405-47D1-A409-AB8FC773D6A8","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"105573c9f8e39ccc12257974c3b01cf155d648c9","datavalue":{"value":"https://doi.org/10.1006/jctb.1993.1005","type":"string"},"datatype":"url"},"type":"statement","id":"Q1204485$0109CC13-D473-4210-B1D9-80E654C5DF46","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"7a60fb2dd71fb2e59186f1b5a9fb3233d312cb6b","datavalue":{"value":"W2036243565","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1204485$EF4F1258-BB63-4D44-9F4B-D5CC7DE12488","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"77eb99ebb1da740e86f757dcd25eb89d4c0c9bf2","datavalue":{"value":"10.1006/JCTB.1993.1005","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1204485$F93A2349-81E4-4CBE-972A-DCFB7EDF6185","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ed996575216dbf00a80f4c47f222846caa9f4d06","datavalue":{"value":{"entity-type":"item","numeric-id":4312248,"id":"Q4312248"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bae4c49bea876625f78fc34a547b44865f233a62","datavalue":{"value":{"amount":"+0.8832820653915405","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":"Q1204485$7C119F34-E7A6-4212-A849-8F8B80FCBA4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a3bc217990edae5a98d43bd71c3151e3aa51d1b7","datavalue":{"value":{"entity-type":"item","numeric-id":4320467,"id":"Q4320467"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ce19d5b7e058dfc8a9a78fac823c2e52f93f775c","datavalue":{"value":{"amount":"+0.8800387382507324","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":"Q1204485$3BE71B04-D9AB-486C-8016-3EFE8EA5C40E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cb8659a093899304958076948e6b9283f60c7df6","datavalue":{"value":{"entity-type":"item","numeric-id":4940031,"id":"Q4940031"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"933f94b2f2f852a04be3d0317cfe89e6d8f9a9c1","datavalue":{"value":{"amount":"+0.8560634851455688","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":"Q1204485$88411C89-4890-4F8B-8AAF-E25C45EBCC10","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c8387b68c54e65cc9a86e97b274bb0a33dbca082","datavalue":{"value":{"entity-type":"item","numeric-id":5443167,"id":"Q5443167"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6d6503e7be337eae3c4cf2ba6968606880b48247","datavalue":{"value":{"amount":"+0.8402025103569031","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":"Q1204485$A12B7E79-7339-48F6-88F4-7ED411BAA9D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d837887575861f75d86eda5ede420a4782133ddc","datavalue":{"value":{"entity-type":"item","numeric-id":4940016,"id":"Q4940016"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dfa8b38394453ff2bed607fe35d9483b9fded6af","datavalue":{"value":{"amount":"+0.8336523771286011","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":"Q1204485$71EB78A0-23F6-4673-87B9-0608957D70F4","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A characterization of well covered graphs of girth 5 or greater","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_characterization_of_well_covered_graphs_of_girth_5_or_greater"}}}}}