Complete k-ary trees and Hamming graphs

被引:0
作者
Choudum, S. A. [1 ]
Lavanya, S. [1 ]
机构
[1] Indian Inst Technol Madras, Dept Math, Chennai 600036, Tamil Nadu, India
来源
AUSTRALASIAN JOURNAL OF COMBINATORICS | 2009年 / 45卷
关键词
D O I
暂无
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
A Hamming graph H(b, n) of base b and dimension n has vertex set {X = x(1)x(2)... x(n) : x(i) is an element of{0, 1,..., b - 1}, for 1 <= i <= n} and edge set {(X, Y) : X and Y differ in exactly one bit position}. In this paper, we are concerned with the following problem: Given positive integers b, k and h, what is the minimum integer m - m( b, k, h) such that the complete k-ary tree, T-h(k), of height h, is a subgraph of H(b, m)? The value m(b, k, h) is known for very few values of b, k and h. We show that (i) m(k, k, h) - h + 1, for every k >= 3, (ii) inverted right perpendicular(log(3) 2)( h + 1) inverted left perpendicular <= m(3, 2, h) = <= inverted right perpendicular2/3(h + 1)inverted left perpendicular (iii)inverted right perpendicular h+1/log(2)b inverted left perpendicular <= m(b, 2, h) <= inverted right perpendicularh + 1/ inverted right perpendicularlog2 binverted left perpendicular inverted left perpendicular , for every b not equal 2(l), and that (iv) inverted right perpendicular h + 1 log(2)b inverted left perpendicular <= m(b, 2, h) <= inverted right perpendicular h+ 2 log(2)b,inverted left perpendicular for every b = 2(l).
引用
收藏
页码:15 / 24
页数:10
相关论文
共 12 条
[1]  
Bang S., 2007, SPECTRAL CHARACTERIZ
[2]   Embedding complete trees into the hypercube [J].
Bezrukov, SL .
DISCRETE APPLIED MATHEMATICS, 2001, 110 (2-3) :101-119
[3]  
Duato J., 2002, INTERCONNECTION NETW
[4]  
Havel I., 1973, CASOPIS PEST MAT, V98, P307
[5]   The pancyclicity and the Hamiltonian-connectivity of the generalized base-b hypercube [J].
Huang, Chien-Hung ;
Fang, Jywe-Fei .
COMPUTERS & ELECTRICAL ENGINEERING, 2008, 34 (04) :263-269
[6]  
IMRICH W, 2000, WIL INT S D, pR13
[7]   Characterizing subgraphs of Hamming graphs [J].
Klavzar, S ;
Peterin, I .
JOURNAL OF GRAPH THEORY, 2005, 49 (04) :302-312
[8]   SYMMETRY IN INTERCONNECTION NETWORKS BASED ON CAYLEY-GRAPHS OF PERMUTATION-GROUPS - A SURVEY [J].
LAKSHMIVARAHAN, S ;
JWO, JS ;
DHALL, SK .
PARALLEL COMPUTING, 1993, 19 (04) :361-407
[9]  
Lakshmivarahan S., 1988, Journal of Supercomputing, V2, P81, DOI 10.1007/BF00127849
[10]  
Leighton FT., 1992, INTRO PARALLEL ALGOR