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

共 23 条

[1] DOMINATION ALTERATION SETS IN GRAPHS [J].

BAUER, D ;

HARARY, F ;

NIEMINEN, J ;

SUFFEL, CL .

DISCRETE MATHEMATICS, 1983, 47 (2-3) :153-161

[2]

Bondy J. A., 2010, GRADUATE TEXTS MATH, V244

[3] On the bondage number of planar and directed graphs [J].

Carlson, Kelli ;

Develin, Mike .

DISCRETE MATHEMATICS, 2006, 306 (8-9) :820-826

[4]

Dunbar JE, 1998, MG TXB PUR APPL MATH, V209, P471

[5] THE BONDAGE NUMBER OF A GRAPH [J].

FINK, JF ;

JACOBSON, MS ;

KINCH, LF ;

ROBERTS, J .

DISCRETE MATHEMATICS, 1990, 86 (1-3) :47-57

[6] Remarks on the bondage number of planar graphs [J].

Fischermann, M ;

Rautenbach, D ;

Volkmann, L .

DISCRETE MATHEMATICS, 2003, 260 (1-3) :57-67

[7]

Gagarin A., 2012, DISCRETE MA IN PRESS

[8]

Gagarin A., 2003, Cubo, V5, P351

[9]

Hartnell BL, 1999, DISCRETE MATH, V197, P409

[10] BOUNDS ON THE BONDAGE NUMBER OF A GRAPH [J].

HARTNELL, BL ;

RALL, DF .

DISCRETE MATHEMATICS, 1994, 128 (1-3) :173-177

← 1 2 3 →