New upper bounds for the bondage number of a graph in terms of its maximum degree and Euler characteristic.

MaRDI QIDQ4683306zbMATH OpenFDO

Authors Jia Huang, J. Shen

Publication date 20 September 2018

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

zbMATH Keywords

bondage numberEuler characteristicEuler formulagenusgirthgraph embeddingordersize

Mathematics Subject Classification ID

Vertex degrees (05C07) Planar graphs; geometric and topological aspects of graph theory (05C10) Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: The bondage number $b(G)$ of a graph $G$ is the smallest number of edges whose removal from $G$ results in a graph with larger domination number. Let $G$ be embeddable on a surface whose Euler characteristic $chi$ is as large as possible, and assume $chileq0$. Gagarin-Zverovich and Huang have recently found upper bounds of $b(G)$ in terms of the maximum degree $Delta(G)$ and the Euler characteristic $chi(G)=chi$. In this paper we prove a better upper bound $b(G)leqDelta(G)+lfloortfloor$ where $t$ is the largest real root of the cubic equation $z^3+z^2+(3chi-8)z+9chi-12=0$; this upper bound is asymptotically equivalent to $b(G)leqDelta(G)+1+lfloorsqrt4-3chifloor$. We also establish further improved upper bounds for $b(G)$ when the girth, order, or size of the graph $G$ is large compared with its Euler characteristic $chi$.

Recommendations

• An improved upper bound for the bondage number of graphs on surfaces
• Note on the bondage number of graphs on topological surfaces
• Upper bounds on the bondage number of a graph
• Upper bounds for the bondage number of graphs on topological surfaces
• A BOUND ON THE BONDAGE NUMBER OF TOROIDAL GRAPHS

Cited in

(5)

• Note on the bondage number of graphs on topological surfaces
• Upper bounds for domination related parameters in graphs on surfaces
• Upper bounds for the bondage number of graphs on topological surfaces
• An improved upper bound for the bondage number of graphs on surfaces
• Upper bounds on the bondage number of a graph

This page was built for publication: New upper bounds for the bondage number of a graph in terms of its maximum degree and Euler characteristic.

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