Upper bounds on the broadcast function using minimum dominating sets

被引：24

作者：

Harutyunyan, Hovhannes A. ^{[2
]}

Liestman, Arthur L. ^{[1
]}

机构：

[1] Simon Fraser Univ, Sch Comp Sci, Burnaby, BC V5A 1S6, Canada

[2] Concordia Univ, Dept Comp Sci & Software Engn, Montreal, PQ H3G 1M8, Canada

来源：

DISCRETE MATHEMATICS | 2012年 / 312卷 / 20期

关键词：

Domination; Domatic number; Broadcast function; Knodel graph; COMMUNICATION;

D O I：

10.1016/j.disc.2012.06.016

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We construct new upper bounds on the broadcast function B(n), the number of edges in a minimum broadcast graph on n vertices, for a large class of integers n. The bounds are obtained by a construction that uses the minimum size of dominating sets for some Knodel graphs. We also determine the domatic number of these graphs. (C) 2012 Elsevier B.V. All rights reserved.

引用

页码：2992 / 2996

页数：5

共 30 条

[1]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theory of NP-Completeness

[2]

Artin M., 1991, ALGEBRA, P58

[3]

Berge C., 1962, THEORY GRAPHS ITS AP

[4]

Bermond J.-C., 1997, International Journal of Foundations of Computer Science, V8, P109, DOI 10.1142/S0129054197000094

[5] SPARSE BROADCAST GRAPHS [J].

BERMOND, JC ;

HELL, P ;

LIESTMAN, AL ;

PETERS, JG .

DISCRETE APPLIED MATHEMATICS, 1992, 36 (02) :97-130

[6]

Cockayne E. J., 1977, Networks, V7, P247, DOI 10.1002/net.3230070305

[7] Compound constructions of broadcast networks [J].

Dinneen, MJ ;

Ventura, JA ;

Wilson, MC ;

Zakeri, G .

DISCRETE APPLIED MATHEMATICS, 1999, 93 (2-3) :205-232

[8] A survey on Knodel graphs [J].

Fertin, G ;

Raspaud, A .

DISCRETE APPLIED MATHEMATICS, 2004, 137 (02) :173-195

[9] Minimum linear gossip graphs and maximal linear (Δ, k)-gossip graphs [J].

Fraigniaud, P ;

Peters, JG .

NETWORKS, 2001, 38 (03) :150-162

[10] METHODS AND PROBLEMS OF COMMUNICATION IN USUAL NETWORKS [J].

FRAIGNIAUD, P ;

LAZARD, E .

DISCRETE APPLIED MATHEMATICS, 1994, 53 (1-3) :79-133

← 1 2 3 →