The bondage number of graphs on topological surfaces and Teschner¡¯s conjecture

详细信息    查看全文

• 作者：Andrei Gagarin^a ; ^{andrei.gagarin@acadiau.ca} ; Vadim Zverovich^b ; ^{vadim.zverovich@uwe.ac.uk}
• 关键词：Bondage number ; Domination number ; Topological surface ; Embedding on a surface ; Euler&rsquo ; s formula ; Triangle-free graphs
• 刊名：Discrete Mathematics
• 出版年：2013
• 出版时间：28 March, 2013
• 年：2013
• 卷：313
• 期：6
• 页码：796-808
• 全文大小：242 K

文摘

The bondage number of a graph is the smallest number of its edges whose removal results in a graph having a larger domination number. We provide constant upper bounds for the bondage number of graphs on topological surfaces, and improve upper bounds for the bondage number in terms of the maximum vertex degree and the orientable and non-orientable genera of graphs. Also, we present stronger upper bounds for graphs with no triangles and graphs with the number of vertices larger than a certain threshold in terms of graph genera. This settles Teschner¡¯s Conjecture in affirmative for almost all graphs. As an auxiliary result, we show tight lower bounds for the number of vertices of graphs 2-cell embeddable on topological surfaces of a given genus.