An improved upper bound for the bondage number of graphs on surfaces

DOI10.1016/J.DISC.2012.05.012MaRDI QIDQ449115zbMATH OpenOpenAlexFDO

Authors Jia Huang

Publication date 12 September 2012

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

Euler characteristicgenusgirthgraph embeddingbondage numberEuler's formula

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) 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. Recently Gagarin and Zverovich showed that, for a graph $G$ with maximum degree $Delta(G)$ and embeddable on an orientable surface of genus $h$ and a non-orientable surface of genus $k$, $b(G)leqminDelta(G)+h+2,Delta+k+1$. They also gave examples showing that adjustments of their proofs implicitly provide better results for larger values of $h$ and $k$. In this paper we establish an improved explicit upper bound for $b(G)$, using the Euler characteristic $chi$ instead of the genera $h$ and $k$, with the relations $chi=2-2h$ and $chi=2-k$. We show that $b(G)leqDelta(G)+lfloorrfloor$ for the case $chileq0$ (i.e. $hgeq1$ or $kgeq2$), where $r$ is the largest real root of the cubic equation $z^3+2z^2+(6chi-7)z+18chi-24=0$. Our proof is based on the technique developed by Carlson-Develin and Gagarin-Zverovich, and includes some elementary calculus as a new ingredient. We also find an asymptotically equivalent result $b(G)leqDelta(G)+lceilsqrt12-6chi,-1/2ceil$ for $chileq0$, and a further improvement for graphs with large girth.

Recommendations

• New upper bounds for the bondage number of a graph in terms of its maximum degree and Euler characteristic.
• Upper bounds for domination related parameters in graphs on surfaces
• Upper bounds for the bondage number of graphs on topological surfaces
• Note on the bondage number of graphs on topological surfaces
• The bondage number of graphs on topological surfaces and Teschner's conjecture

Cites work

• scientific article; zbMATH DE number 425998 (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
• Graphs on surfaces
• On the bondage number of planar and directed graphs
• On the complexity of the bondage and reinforcement problems
• The bondage number of a graph
• Upper bounds for the bondage number of graphs on topological surfaces

Cited in

(10)

• Upper bounds on the bondage number of a graph
• Structurally stable output regulation of nonlinear systems
• Improved bounds for bipartite matching on surfaces
• On bondage numbers of graphs: a survey with some comments
• Note on the bondage number of graphs on topological surfaces
• Upper bounds for the bondage number of graphs on topological surfaces
• The bondage number of graphs on topological surfaces and Teschner's conjecture
• New upper bounds for the bondage number of a graph in terms of its maximum degree and Euler characteristic.
• Upper bounds for domination related parameters in graphs on surfaces
• Upper bounds on the maximum degree of class two graphs on surfaces

This page was built for publication: An improved upper bound for the bondage number of graphs on surfaces

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