Upper bounds for the bondage number of graphs on topological surfaces

DOI10.1016/J.DISC.2011.10.018zbMATH Open1277.05125arXiv1012.4117OpenAlexW2169487918MaRDI QIDQ385372FDOQ385372

Andrei Gagarin, Vadim Zverovich

Publication date: 2 December 2013

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

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

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

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)

Cites Work

• The Jordan-Schonflies Theorem and the Classification of Surface
• The bondage number of a graph
• Bounds on the bondage number of a graph
• Domination alteration sets in graphs
• Title not available (Why is that?)
• Bondage number of planar graphs
• Remarks on the bondage number of planar graphs
• On the bondage number of planar and directed graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (6)

• Upper bounds on the bondage number of a graph
• 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
• The bondage number of graphs on topological surfaces and Teschner's conjecture
• Upper bounds on the maximum degree of class two graphs on 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)