Strength and fractional arboricity of complementary graphs
Let \(o(G)\) denote the number of components of a graph \(G\). The strength, \(s(G)\), and the fractional arboricity, \(a(G)\), of \(G\) are given by \(s(G) = \min |S |/ (o(G - S) - o(G))\), minimum being taken over all subsets \(S\) of \(E(G)\) with \(o(G - S) > o(G)\), and \(a(G) = \min |E(H) |/ (|V(H) |-o(H))\), minimum being taken over all subgraphs \(H\) with \(|V(H) |> o(H)\), respectively. Nordhaus-Gaddum type inequalities on \(s(G)\) and \(a(G)\) are presented.
scientific article; zbMATH DE number 790549
scientific article