Domination in bipartite graphs

被引：4

作者：

Harant, Jochen ^{[1
]}

Rautenbach, Dieter ^{[1
]}

机构：

[1] Tech Univ Ilmenau, Inst Math, D-98684 Ilmenau, Germany

来源：

DISCRETE MATHEMATICS | 2009年 / 309卷 / 01期

关键词：

Domination number; Cycle length; Bipartite; Probabilistic method; NUMBER;

D O I：

10.1016/j.disc.2007.12.051

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We prove that the domination 3 number of a graph of order n and minimum degree at least 2 that does not contain cycles of length 4, 5, 7, 10 or 13 is at most 3/8n. Furthermore, we derive upper bounds on the domination number of bipartite graphs of given minimum degree. (C) 2008 Elsevier B.V. All rights reserved.

引用

页码：113 / 122

页数：10

共 18 条

[1]

Alon Noga, 1992, The Probabilistic Method

[2]

AMAUTOV VI, 1974, PRIKL MAT PROGRAMM, V11, P3

[3]

Blank M.M., 1973, PRIKL MAT PROGRAMMIR, P3

[4] BOUNDS ON THE DOMINATION NUMBER OF A GRAPH [J].

BRIGHAM, RC ;

DUTTON, RD .

QUARTERLY JOURNAL OF MATHEMATICS, 1990, 41 (163) :269-275

[5]

CARO Y, 1985, ARS COMBINATORIA, V20, P167

[6]

Caro Y., 1990, INT J MATH MATH SCI, V13, P205, DOI [10.1155/S016117129000031X, DOI 10.1155/S016117129000031X, 10.1155S016117129000031X////]

[7]

Gerlach T., 2002, Discussiones Mathematicae Graph Theory, V22, P229, DOI 10.7151/dmgt.1171

[8]

HARANT J, 2001, ANN COMB, V5, P175, DOI DOI 10.1007/PL00001298

[9]

Haynes T. W., 1998, DOMINATION GRAPHS AD

[10] Domination in a graph with a 2-factor [J].

Kawarabayashi, K ;

Plummer, MD ;

Saito, A .

JOURNAL OF GRAPH THEORY, 2006, 52 (01) :1-6

← 1 2 →