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

被引：2

作者：

Gagarin, Andrei ^{[1
]}

Zverovich, Vadim ^{[2
]}

机构：

[1] Acadia Univ, Dept Math & Stat, Wolfville, NS B4P 2R6, Canada

[2] Univ W England, Dept Math & Stat, Bristol BS16 1QY, Avon, England

来源：

DISCRETE MATHEMATICS | 2013年 / 313卷 / 06期

关键词：

Bondage number; Domination number; Topological surface; Embedding on a surface; Euler's formula; Triangle-free graphs; PLANAR GRAPHS; GENUS;

D O I：

10.1016/j.disc.2012.12.018

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

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. (C) 2012 Elsevier B.V. All rights reserved.

引用

页码：796 / 808

页数：13

共 40 条

[21] A BOUND ON THE BONDAGE NUMBER OF TOROIDAL GRAPHS* [J].

Hou, Jianfeng ;

Liu, Guizhen .

DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2012, 4 (03)

[22] On the average lower bondage number of graphs under join and corona operations [J].

Turaci, Tufan ;

Kocay, Gamze .

NUMERICAL METHODS FOR PARTIAL DIFFERENTIAL EQUATIONS, 2022, 38 (03) :654-665

[23] Bondage Number of Planar Graphs without Small Cycles [J].

Hou, Jianfeng ;

Liu, Guizhen ;

Wu, Jianliang .

UTILITAS MATHEMATICA, 2011, 84 :189-199

[24] m-ETERNAL TOTAL BONDAGE NUMBER IN CIRCULANT GRAPHS [J].

Pushpam, P. Boushini Leely ;

Shanthi, P. A. .

TWMS JOURNAL OF APPLIED AND ENGINEERING MATHEMATICS, 2025, 15 (05) :1217-1229

[25] About AutoGraphiX Conjecture on Domination Number and Remoteness of Graphs [J].

Pei, Lidan .

MATHEMATICS, 2022, 10 (19)

[26] The Number of Defective Colorings of Graphs on Surfaces [J].

Rackham, Tom .

JOURNAL OF GRAPH THEORY, 2011, 68 (02) :129-136

[27] Lower bound number of irreducible graphs on surfaces [J].

Liu, Y ;

Liu, YP .

ACTA MATHEMATICA SCIENTIA, 1998, 18 (03) :333-339

[28] k-CHROMATIC NUMBER OF GRAPHS ON SURFACES [J].

Dvorak, Zdenek ;

Skrekovski, Riste .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2009, 23 (01) :477-486

[29] Number of Embeddings of Wheel Graphs on Surfaces of Small Genus [J].

Yang, Yan ;

Liu, Yanpei .

ARS COMBINATORIA, 2011, 101 :225-249

[30] A disproof of Henning's conjecture on irredundance perfect graphs [J].

Volkmann, L ;

Zverovich, VE .

DISCRETE MATHEMATICS, 2002, 254 (1-3) :539-554

← 1 2 3 4 →