Strength and fractional arboricity of complementary graphs

DOI10.1016/0012-365X(95)00012-LMaRDI QIDQ1897432zbMATH OpenFDO

Authors Hong-Jian Lai, Guoqing Weng

Publication date 12 February 1996

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(95)00012-L

zbMATH Keywords

fractional arboricityNordhaus-Gaddum type inequalitiesnumber of componentsstrength

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35)

Review text

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.

Recommendations

• Fractional arboricity, strength, and principal partitions in graphs and matroids
• Fractional arboricity, strength and eigenvalues of graphs with fixed girth or clique number
• Arboricity and complement of a graph
• Fractional Vertex Arboricity of Graphs
• On linear vertex‐arboricity of complementary graphs
• Fractional dominations and fractional total dominations of graph complements
• scientific article; zbMATH DE number 1123795
• On the Strongly Connected and Biconnected Components of the Complement of Graphs
• scientific article; zbMATH DE number 1743772
• A result on the strength of graphs by factorizations of complete graphs

Cites work

• Fractional arboricity, strength, and principal partitions in graphs and matroids
• Graph theory
• scientific article; zbMATH DE number 4130426 (Why is no real title available?)
• scientific article; zbMATH DE number 436073 (Why is no real title available?)
• scientific article; zbMATH DE number 3750966 (Why is no real title available?)
• scientific article; zbMATH DE number 36698 (Why is no real title available?)
• scientific article; zbMATH DE number 68345 (Why is no real title available?)
• scientific article; zbMATH DE number 4121463 (Why is no real title available?)
• On Complementary Graphs
• Optimal attack and reinforcement of a network

Cited in

(2)

• Fractional arboricity, strength, and principal partitions in graphs and matroids
• Arboricity and complement of a graph

This page was built for publication: Strength and fractional arboricity of complementary graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1897432)