Fractional Gallai-Edmonds decomposition and maximal graphs on fractional matching number (Q2185816)

The paper analyses the Gallai-Edmonds decomposition of a graph with fractional matching and characterizes the Turán 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án 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án number, the saturation number and extremal graphs as well.