Covering a graph with cuts of minimum total size

DOI10.1016/S0012-365X(00)00367-8MaRDI QIDQ5939921zbMATH OpenOpenAlexFDO

Authors Zoltán Füredi, André Kündgen

Publication date 23 July 2001

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0012-365x(00)00367-8

zbMATH Keywords

bandwidth-sumchromatic numbercut-covergeometric representationgraph coveringNordhaus-Gaddum typeplanar graphsrandom graphTurán graph

Mathematics Subject Classification ID

Distance in graphs (05C12) Coloring of graphs and hypergraphs (05C15) Extremal problems in graph theory (05C35) Graph representations (geometric and intersection representations, etc.) (05C62) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Random graphs (graph-theoretic aspects) (05C80)

Review text

A cut in a graph \(G\) is the set of all edges between some set \(S\) of vertices of \(G\) and its complement \(\overline S\) in \(V(G)\). A cut-cover of \(G\) is a collection of cuts covering all edges of \(G\), its size is the sum of the cardinalities of the cuts, and the cut-cover size \(\text{cs}(G)\) of \(G\) is the minimum size of a cut-cover of \(G\). General bounds on \(\text{cs}(G)\) are given, for instance \(2e(G)- \text{Cut}(G)\leq \text{cs}(G)\leq 2e(G)- \text{Cut}'(G)\) (where \(\text{Cut}(G)\) resp. \(\text{Cut}'(G)\) denotes the maximal cardinality of an arbitrary cut resp. of a cut defined by a stable set of vertices) and another one of Nordhaus-Gaddum type combining \(\text{cs}(G)\) and \(\text{cs}(\overline G)\). Precise values of \(\text{cs}(G)\) for special graphs are given as well as sharp bounds for classes of graphs such as 4-colorable graphs. While in general the problem of determining \(\text{cs}(G)\) is NP-complete, \(\text{cs}(G)\) of planar graphs can be found in polynomial time. Connections of \(\text{cs}(G)\) are drawn to a geometric representation of \(G\) and to the bandwidth-sum of \(G\).

Recommendations

• A bound on the total size of a cut cover
• A note on the minimum cut cover of graphs
• On the Number of Minimum Cuts in a Graph
• Minimal cut cover of a graph with an application to the testing of electronic boards
• Covering complete hypergraphs with cuts of minimum total size

Cited in

(13)

• Minimal cut cover of a graph with an application to the testing of electronic boards
• A note on the minimum cut cover of graphs
• An overview of graph covering and partitioning
• On fractional cut covers
• On biclique coverings
• A bound on the total size of a cut cover
• Fractional covering by cuts
• scientific article; zbMATH DE number 3906531 (Why is no real title available?)
• scientific article; zbMATH DE number 1843998 (Why is no real title available?)
• Covering complete \(r\)-graphs with spanning complete \(r\)-partite \(r\)-graphs
• scientific article; zbMATH DE number 6783459 (Why is no real title available?)
• Covering complete hypergraphs with cuts of minimum total size
• On the biclique cover of the complete graph

This page was built for publication: Covering a graph with cuts of minimum total size

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