The domination number of exchanged hypercubes

被引：23

作者：

Klavzar, Sandi ^{[1
,2
,3
]}

Ma, Meijie ^{[4
]}

机构：

[1] Univ Ljubljana, Fac Math & Phys, Ljubljana 61000, Slovenia

[2] Univ Maribor, Fac Nat Sci & Math, Maribor, Slovenia

[3] Inst Math Phys & Mech, Ljubljana, Slovenia

[4] Zhejiang Normal Univ, Dept Math, Jinhua 321004, Zhejiang, Peoples R China

来源：

INFORMATION PROCESSING LETTERS | 2014年 / 114卷 / 04期

基金：

中国国家自然科学基金;

关键词：

Interconnection networks; Hypercube; Exchanged hypercube; Domination number; Hamming code; HAMILTONIAN CYCLES;

D O I：

10.1016/j.ipl.2013.12.005

中图分类号：

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

学科分类号：

0812 ;

摘要：

Exchanged hypercubes (Loh et al., 2005 [13]) are spanning subgraphs of hypercubes with about one half of their edges but still with many desirable properties of hypercubes. Lower and upper bounds on the domination number of exchanged hypercubes are proved which in particular imply that gamma(EH(2, t)) = 2(t+1) holds for any t >= 2. Using Hamming codes we also prove that gamma (EH(s, 2(k) -1)) <= (2(s) - 2(k))gamma(Q(2k-1)) + (gamma(Q(s)(-)) + 1) holds for s >= k >= 3. (C) 2013 Elsevier B.V. All rights reserved.

引用

页码：159 / 162

页数：4

共 22 条

[1]

Ananchuen N, 2011, STRUCTURAL ANALYSIS OF COMPLEX NETWORKS, P73, DOI 10.1007/978-0-8176-4789-6_4

[2] Linearly many faults in dual-cube-like networks [J].

Angjeli, Ariana ;

Cheng, Eddie ;

Liptak, Laszlo .

THEORETICAL COMPUTER SCIENCE, 2013, 472 :1-8

[3]

Arumugam S., 1998, J. Indian Math. Soc., New Ser., V65, P31

[4] On the domination number and the 2-packing number of Fibonacci cubes and Lucas cubes [J].

Castro, Aline ;

Klavzar, Sandi ;

Mollard, Michel ;

Rho, Yoomi .

COMPUTERS & MATHEMATICS WITH APPLICATIONS, 2011, 61 (09) :2655-2660

[5] Conditional edge-fault-tolerant Hamiltonicity of dual-cubes [J].

Chen, Jheng-Cheng ;

Tsai, Chang-Hsiung .

INFORMATION SCIENCES, 2011, 181 (03) :620-627

[6] A comment on "The exchanged hypercube" [J].

Chen, Yu-Wei .

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2007, 18 (04) :576-576

[7]

Dvorák T, 2003, DISCRETE MATH, V262, P121

[8] INDEPENDENT DOMINATION IN HYPERCUBES [J].

HARARY, F ;

LIVINGSTON, M .

APPLIED MATHEMATICS LETTERS, 1993, 6 (03) :27-28

[9]

Haynes TW, 1998, Fundamentals of domination in graphs, V1st, DOI [DOI 10.1201/9781482246582, 10.1201/9781482246582]

[10] Generalized measures of fault tolerance in exchanged hypercubes [J].

Li, Xiang-Jun ;

Xu, Jun-Ming .

INFORMATION PROCESSING LETTERS, 2013, 113 (14-16) :533-537

← 1 2 3 →