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

DOI10.1016/J.DISC.2012.05.012zbMATH Open1248.05140arXiv1111.5629OpenAlexW2020447305MaRDI QIDQ449115FDOQ449115

Authors: Jia Huang 

Publication date: 12 September 2012

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 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.

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

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

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)

Cites Work

• Graphs on surfaces
• On the complexity of the bondage and reinforcement problems
• Title not available (Why is that?)
• 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
• On the bondage number of planar and directed graphs
• Upper bounds for the bondage number of graphs on topological surfaces
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (6)

• 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
• 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: 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)