Upper bounds for the bondage number of graphs on topological surfaces

DOI10.1016/J.DISC.2011.10.018MaRDI QIDQ385372zbMATH OpenOpenAlexFDO

Authors Andrei Gagarin, Vadim Zverovich

Publication date 2 December 2013

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1012.4117

zbMATH Keywords

domination numberbondage numberEuler's formulatopological surfaceembedding on a surface

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Vertex degrees (05C07)

Abstract: The bondage number b(G) of a graph G is the smallest number of edges of G whose removal from G results in a graph having the domination number larger than that of G. We show that, for a graph G having the maximum vertex degree $Delta(G)$ and embeddable on an orientable surface of genus h and a non-orientable surface of genus k, $b(G)leminDelta(G)+h+2,Delta(G)+k+1$. This generalizes known upper bounds for planar and toroidal graphs.

Recommendations

• An improved upper bound for the bondage number of graphs on surfaces
• Note on the bondage number of graphs on topological surfaces
• New upper bounds for the bondage number of a graph in terms of its maximum degree and Euler characteristic.
• Upper bounds for the domination subdivision and bondage numbers of graphs on topological surfaces.
• A BOUND ON THE BONDAGE NUMBER OF TOROIDAL GRAPHS

Cites work

• scientific article; zbMATH DE number 1109414 (Why is no real title available?)
• scientific article; zbMATH DE number 1124610 (Why is no real title available?)
• scientific article; zbMATH DE number 825127 (Why is no real title available?)
• scientific article; zbMATH DE number 3378931 (Why is no real title available?)
• Bondage number of planar graphs
• Bounds on the bondage number of a graph
• Domination alteration sets in graphs
• On the bondage number of planar and directed graphs
• Remarks on the bondage number of planar graphs
• The Jordan-Schonflies Theorem and the Classification of Surface
• The bondage number of a graph

Cited in

(11)

• New upper bounds for the bondage number of a graph in terms of its maximum degree and Euler characteristic.
• On bondage number of toroidal graphs
• Upper bounds on the bondage number of a graph
• Note on the bondage number of graphs on topological surfaces
• Upper bounds on the bondage number of the strong product of a graph and a tree
• An improved upper bound for the bondage number of graphs on surfaces
• On bondage numbers of graphs: a survey with some comments
• Upper bounds for domination related parameters in graphs on surfaces
• The bondage number of graphs on topological surfaces and Teschner's conjecture
• Upper bounds on the maximum degree of class two graphs on surfaces
• Upper bounds for the domination subdivision and bondage numbers of graphs on topological surfaces.

This page was built for publication: Upper bounds for the bondage number of graphs on topological surfaces

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