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 条

[31] Upper bounds for the forgotten topological index of graphs with given domination number [J].

Alyar, S. ;

Khoeilar, R. .

ASIAN-EUROPEAN JOURNAL OF MATHEMATICS, 2021, 14 (09)

[32] RETRACTED ARTICLE: An investigation of unicyclic graphs in which the isolate bondage number is equal to three in graph network theory [J].

B. K. Keerthiga Priyatharsini ;

S. Velammal .

Journal of Ambient Intelligence and Humanized Computing, 2021, 12 :5743-5749

[33] A note on Reed's conjecture for triangle-free graphs [J].

Abrishami, Gholamreza ;

Erfanian, Ahmad .

DISCRETE MATHEMATICS, 2023, 346 (12)

[34] HADWIGER'S CONJECTURE FOR SOME HEREDITARY CLASSES OF GRAPHS: A SURVEY [J].

Cameron, Kathie ;

Vuskovic, Kristina .

BULLETIN OF THE EUROPEAN ASSOCIATION FOR THEORETICAL COMPUTER SCIENCE, 2020, 131 (131) :1-18

[35] RETRACTED: An investigation of unicyclic graphs in which the isolate bondage number is equal to three in graph network theory (Retracted Article) [J].

Priyatharsini, B. K. Keerthiga ;

Velammal, S. .

JOURNAL OF AMBIENT INTELLIGENCE AND HUMANIZED COMPUTING, 2021, 12 (06) :5743-5749

[36] Green's Conjecture for curves on rational surfaces with an anticanonical pencil [J].

Lelli-Chiesa, Margherita .

MATHEMATISCHE ZEITSCHRIFT, 2013, 275 (3-4) :899-910

[37] Application of upper and lower bounds for the domination number to Vizing's conjecture [J].

Clark, WE ;

Ismail, MEH ;

Suen, S .

ARS COMBINATORIA, 2003, 69 :97-108

[38] Green's conjecture for curves on arbitrary K3 surfaces [J].

Aprodu, Marian ;

Farkas, Gavril .

COMPOSITIO MATHEMATICA, 2011, 147 (03) :839-851

[39] Maximum average degree of list-edge-critical graphs and Vizing's conjecture [J].

Harrelson, Joshua ;

Reavis, Hannah .

ELECTRONIC JOURNAL OF GRAPH THEORY AND APPLICATIONS, 2022, 10 (02) :385-392

[40] Vizing's conjecture: A two-thirds bound for claw-free graphs [J].

Krop, Elliot .

DISCRETE APPLIED MATHEMATICS, 2017, 230 :162-165

← 1 2 3 4 →