The discipline number of a graph

DOI10.1016/0012-365X(90)90360-TMaRDI QIDQ1174136zbMATH OpenOpenAlexFDO

Authors Vašek Chvátal, William Cook

Publication date 25 June 1992

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365x(90)90360-t

zbMATH Keywords

bondage numbercomplete multipartite graphsdiscipline numberdomination number

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (05C99) Graph theory (including graph drawing) in computer science (68R10)

Review text

The domination number \(\gamma(G)\) of a graph \(G\) is the size of a smallest set \(D\) of vertices such that every vertex outside \(D\) has at least one neighbour in \(D\). The bondage number \(b(G)\) is the least number of edges whose deletion increases \(\gamma(G)\). The solution of the dual problem to the linear programming relaxation of computing the bondage number is called the discipline number of \(G\). Here the authors state some results on the discipline number of complete multipartite graphs.

Recommendations

• scientific article; zbMATH DE number 876673
• The bondage number of a graph
• On the bondage number of a graph
• New results about the bondage number of a graph

Cites work

• Domination alteration sets in graphs
• scientific article; zbMATH DE number 3861143 (Why is no real title available?)
• On graphs having domination number half their order
• Optimization of a 532-city symmetric traveling salesman problem by branch and cut
• The bondage number of a graph

Cited in

(7)

• A bound on the size of a graph with given order and bondage number
• Bounds on the bondage number of a graph
• Vašek Chvátal: a very short introduction (on the occasion of his 60th birthday)
• Integer programming methods for solving binary interdiction games
• Integer Programming Formulations for Minimum Spanning Tree Interdiction
• Solving graph partitioning on sparse graphs: cuts, projections, and extended formulations
• Bibliography on domination in graphs and some basic definitions of domination parameters

This page was built for publication: The discipline number of a graph

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