Efficient domination in circulant graphs with two chord lengths

被引：38

作者：

Obradovic, Nenad ^{[1
]}

Peters, Joseph ^{[1
]}

Ruzic, Goran ^{[1
]}

机构：

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

来源：

INFORMATION PROCESSING LETTERS | 2007年 / 102卷 / 06期

基金：

加拿大自然科学与工程研究理事会;

关键词：

circulant graph; efficient domination; combinatorial problems;

D O I：

10.1016/j.ipl.2007.02.004

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

Domination is an important property in the design of efficient computer interconnection networks. We provide a complete characterization of circulant graphs with two chord lengths that admit an efficient dominating set. In particular, for 3-regular and 4-regular circulant graphs, we give necessary and sufficient conditions for the existence of efficient dominating sets and we describe their exact structure according to the relationship between chords. (c) 2007 Elsevier B.V. All rights reserved.

引用

页码：253 / 258

页数：6

共 13 条

[1] HAMILTONIAN DECOMPOSITION OF CAYLEY-GRAPHS OF DEGREE-4 [J].

BERMOND, JC ;

FAVARON, O ;

MAHEO, M .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1989, 46 (02) :142-153

[2] DISTRIBUTED LOOP COMPUTER-NETWORKS - A SURVEY [J].

BERMOND, JC ;

COMELLAS, F ;

HSU, DF .

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 1995, 24 (01) :2-10

[3]

CHEN CC, 1981, LECT NOTES MATH, V884, P23

[4] Efficient dominating sets in Cayley graphs [J].

Dejter, IJ ;

Serra, O .

DISCRETE APPLIED MATHEMATICS, 2003, 129 (2-3) :319-328

[5]

GU W, 2002, INDEPENDENT PERFECT

[6]

GVOZDJAK P, 2001, SIROCCO 8, P195

[7] Independent perfect domination sets in Cayley graphs [J].

Lee, J .

JOURNAL OF GRAPH THEORY, 2001, 37 (04) :213-219

[8]

Livingston M., 1990, C NUMERANTUM, V79, P187

[9]

Livingston M., 1994, C NUMER, V105, P116

[10]

Masters J. D., 1996, C NUMER, V118, P49

← 1 2 →