{"entities":{"Q2185816":{"pageid":2196559,"ns":120,"title":"Item:Q2185816","lastrevid":82581062,"modified":"2026-05-06T21:14:56Z","type":"item","id":"Q2185816","labels":{"en":{"language":"en","value":"Fractional Gallai-Edmonds decomposition and maximal graphs on fractional matching number"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7209322"}},"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":"Q2185816$624AAA7C-D3AD-4817-8705-BF29E51BCA1A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9a73473ac08d3849c1b12e47c5559bf96ac46866","datavalue":{"value":{"text":"Fractional Gallai-Edmonds decomposition and maximal graphs on fractional matching number","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2185816$A37522FF-2EDE-48BD-A420-08164A439199","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"882a1ce51b6f99d289a4ada94952c3aa612648ba","datavalue":{"value":"1472.90113","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2185816$0C2FFC8B-6F6D-4990-87E2-4DA44BAEF858","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9e2df8497ba87677af756da5ca2d92625d399449","datavalue":{"value":{"entity-type":"item","numeric-id":234331,"id":"Q234331"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2185816$25B67F0E-9CD9-4D3B-A100-FE9BD4871486","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"707194fa58b2c7d40745486b1c6cafad69b8102a","datavalue":{"value":{"entity-type":"item","numeric-id":2185815,"id":"Q2185815"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2185816$8D8A5EC4-FC62-4654-8256-8EA2C46BAB33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3e710cb466bba10357dc5ae46af116bd3c749ada","datavalue":{"value":{"entity-type":"item","numeric-id":2022515,"id":"Q2022515"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2185816$071C5669-675E-4D2D-8482-D2F227790477","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"dcf8815e3b257674fa147da7a4e7c92c91c0b3e3","datavalue":{"value":{"entity-type":"item","numeric-id":185429,"id":"Q185429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2185816$DA70DEB4-8A4C-4CA1-9D45-E061D3A6C1F2","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1c385d77ffcc13ea578b29961aa32ef091af481f","datavalue":{"value":{"time":"+2020-06-05T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2185816$6B6148D5-F6E7-4130-8D3D-B0C0D632398B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"87a27c4d090f2d72312dbb4b84dc50a052bf047b","datavalue":{"value":"The paper analyses the Gallai-Edmonds decomposition of a graph with fractional matching and characterizes the Tur\u00e1n number, saturation number and extremal graphs with respect to fractional matching.  A fractional matching extends the notion of a classical matching by assigning to each edge \\(e\\) of a graph \\(G\\) a real number \\(f(e)\\) from the interval \\([0,1]\\) such that for each vertex \\(v\\), \\(\\sum_{e\\in\\Gamma(v)} f (e) \\le 1\\). The fractional matching number \\(\\mu_f(G)\\) of \\(G\\) is the supremum of \\(\\sum_{e\\in E(G)} f(e)\\) over all fractional matchings \\(f\\) of \\(G\\). A Gallai-Edmonds decomposition is a partition \\((C_f(G), A_f(G), D_f(G))\\), where \\(D_f(G)\\) is the set of vertices which are unsaturated by some maximum matching of \\(G\\), \\(A_f(G)\\) are vertices adjacent to them and \\(C_f(G)\\) are the remaining vertices. This partition can be naturally generalized to the fractional Gallai-Edmonds decomposition if we consider a maximum fractional matching instead. A graph \\(G\\) is maximal on \\(\\mu_f(G)\\) if any addition of an edge increases the fractional matching number \\(\\mu_f(G)\\). The Tur\u00e1n number is the maximum of edge numbers of maximal graphs and the saturation number is the minimum of edge numbers of maximal graphs. The authors show that the fractional Gallai-Edmonds decomposition can be done in a polynomial time. As a result, they obtain a characterization of maximal graphs, the Tur\u00e1n number, the saturation number and extremal graphs as well.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2185816$1C76B7CC-769F-44EF-BAA9-BA49F35E0EC3","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"d7f1127c63fcb04479eae252afd6f073fe30fe10","datavalue":{"value":{"entity-type":"item","numeric-id":187117,"id":"Q187117"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2185816$437C6DAF-AA63-49B6-AC05-C551EAC4731C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2185816$54AA1395-5787-41A2-90A7-54C1862B5C5D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2185816$A9187B6C-519D-487D-AA46-5E586BF1FEBD","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"714af7e54ef7575972a15d46c1d0893b794794b4","datavalue":{"value":"7209322","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2185816$788D516A-AA9D-4BE7-8B2D-AB777E2802B2","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"873c3f23e825881d1cfc5006ee4e0b09c4234317","datavalue":{"value":"fractional matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q2185816$6EC7801C-389B-4C78-9F52-D05F7046B514","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"37986fb309da9884de46b2ccff4d89a7f5190411","datavalue":{"value":"fractional Gallai-Edmonds decomposition","type":"string"},"datatype":"string"},"type":"statement","id":"Q2185816$995D4D05-B962-43EB-8897-C775A1901B74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ee27b826a296675554930a3ca361eed592537d8","datavalue":{"value":"maximal graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2185816$6FD71DC8-C786-4EDC-8568-8B5674A91778","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3df666cf44ac44f2322f39855869ccee5bfa7cd6","datavalue":{"value":"Tur\u00e1n number","type":"string"},"datatype":"string"},"type":"statement","id":"Q2185816$DC117A2D-4CB5-49E8-B9A0-A7FDA2E07E70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5ba3d08eaa1a82a6fcaa6e6a2a62c141a93978c4","datavalue":{"value":"saturation number","type":"string"},"datatype":"string"},"type":"statement","id":"Q2185816$405719C9-0135-4190-B88E-4DB927052468","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":"Q2185816$2D440355-0DFA-4B83-8BDD-79AB25EEF791","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"66f1f40db441e24df844289a39bf6eec26489246","datavalue":{"value":"https://doi.org/10.1007/s10878-020-00566-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q2185816$BFE4051E-E197-4780-8FCB-D73716DB76C0","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"862d2db9cf03f9876201bf2eefc79645daa19197","datavalue":{"value":"W3015604112","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2185816$02930F3A-326C-45A3-8A64-CE9500CEBCFE","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1cb44fa19ef432ebe70a929dc7ab6c3c9375a250","datavalue":{"value":{"entity-type":"item","numeric-id":3722536,"id":"Q3722536"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2185816$35FDF93A-074F-4AC4-9A48-287E744D5F99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2e3a36dc4ee0da40f098fb6f68de4d23db5ec320","datavalue":{"value":{"entity-type":"item","numeric-id":4798195,"id":"Q4798195"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2185816$43DEC285-F329-4F52-B9A4-3EF3D6D068FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"14227f475a06363f0739bd70616a51a22678f4ba","datavalue":{"value":{"entity-type":"item","numeric-id":2410101,"id":"Q2410101"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2185816$0377536B-B28D-4ACB-9A0C-56B3618F8C98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"45751b7cfe71cdfadd4888639c525aec369baef3","datavalue":{"value":{"entity-type":"item","numeric-id":1682886,"id":"Q1682886"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2185816$10C0CC47-1FB3-4BFB-8A79-81CCC52D4C90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"595ef40252c06e8b283a9bc7081da68f4bc9e1fd","datavalue":{"value":{"entity-type":"item","numeric-id":2551474,"id":"Q2551474"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2185816$A4C3A7AC-B551-4FBB-84C4-E7F18AEE9CBF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c3eca1f792744dc0b3f0be36615602475f01c97","datavalue":{"value":{"entity-type":"item","numeric-id":1098861,"id":"Q1098861"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2185816$C932DB68-D171-412D-9827-B31B100EED20","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8c1dc564d3983acab7316fb57d8ba472cdcda5d5","datavalue":{"value":"10.1007/S10878-020-00566-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2185816$C21EB25D-AB05-4190-902A-8C27600189C6","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"567903af32fc571c9314c9cb380a2381105c4843","datavalue":{"value":{"entity-type":"item","numeric-id":4798195,"id":"Q4798195"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f4d22b18bf19815c6b3c0dc51a5915d6c21e8ea4","datavalue":{"value":{"amount":"+0.8697782754898071","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":"Q2185816$DE90F9D9-3CFE-4130-8F4B-0FFCBF88A731","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"43c3ba4c9e384f6fdc6267d3e1a8c9ad425863ea","datavalue":{"value":{"entity-type":"item","numeric-id":1098861,"id":"Q1098861"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fb9f9484f95813ca79e0c1df9f292191e7b6adb1","datavalue":{"value":{"amount":"+0.862510085105896","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":"Q2185816$30E07D3B-0B88-4EEF-AA15-C55440DB8EEC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"47861ac477d308860e6aad2436a991da2e39e523","datavalue":{"value":{"entity-type":"item","numeric-id":2075471,"id":"Q2075471"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1f580a52a5f0bff789d54f23504b2e80987887a5","datavalue":{"value":{"amount":"+0.8148064017295837","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":"Q2185816$D92A15D0-F55D-4105-9F11-7C1BE4D2001C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d4514ec0092a1237074db0ea05f3a13bf9ec1da1","datavalue":{"value":{"entity-type":"item","numeric-id":2078848,"id":"Q2078848"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f9a3d239803fc3bf8a54b71a1d957f52374f8368","datavalue":{"value":{"amount":"+0.8017126321792603","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":"Q2185816$6A80DA60-63AC-4D5F-B170-1D2C20153210","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"96fd278f452758ac5c16cbc49d1f2594075498da","datavalue":{"value":{"entity-type":"item","numeric-id":2345617,"id":"Q2345617"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d85f1aab22bf321995aa202c9aebad9b55854788","datavalue":{"value":{"amount":"+0.7894505262374878","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":"Q2185816$ACF81AAE-8689-4796-AA24-A64B1A61E00F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Fractional Gallai-Edmonds decomposition and maximal graphs on fractional matching number","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Fractional_Gallai-Edmonds_decomposition_and_maximal_graphs_on_fractional_matching_number"}}}}}