Hypercubes as direct products

被引：44
作者：
Bresar, B
Imrich, W
Klavzar, S
Zmazek, B
机构：
[1] Univ Maribor, FEECS, SI-2000 Maribor, Slovenia
[2] Univ Leoben, A-8700 Leoben, Austria
[3] Univ Maribor, Dept Math & Comp Sci, PeF, SI-2000 Maribor, Slovenia
[4] Univ Maribor, FME, SI-2000 Maribor, Slovenia
来源：
SIAM JOURNAL ON DISCRETE MATHEMATICS | 2005年 / 18卷 / 04期
关键词：
direct product; hypercube; automorphism; involution;
D O I：
10.1137/S0895480103438358
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
Let G be a connected bipartite graph. An involution alpha of G that preserves the bipartition of G is called bipartite. Let G(alpha) be the graph obtained from G by adding to G the natural perfect matching induced by alpha. We show that the k- cube Q(k) is isomorphic to the direct product G x H if and only if G is isomorphic to Q(alpha) (k- 1) for some bipartite involution alpha of Q(k- 1) and H = K-2.
引用
收藏
页码：778 / 786
页数：9
相关论文
共 23 条
[1]  
Albert MH, 2001, DISCRETE MATH, V232, P1
[2]  
BRESAR B, 2005, IN PRESS DISCUSS MAT, V25
[3]   The ultimate categorical independence ratio of a graph [J].
Brown, JI ;
Nowakowski, RJ ;
Rall, D .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 1996, 9 (02) :290-300
[4]   FINDING THE PRIME FACTORS OF STRONG DIRECT-PRODUCT GRAPHS IN POLYNOMIAL-TIME [J].
FEIGENBAUM, J ;
SCHAFFER, AA .
DISCRETE MATHEMATICS, 1992, 109 (1-3) :77-102
[5]  
GRAHAM RL, 1970, NY ACAD SCI, V175, P170
[6]   APPLICATIONS OF PRODUCT COLORING [J].
GREENWELL, D ;
LOVASZ, L .
ACTA MATHEMATICA ACADEMIAE SCIENTIARUM HUNGARICAE, 1974, 25 (3-4) :335-340
[7]  
Hell P., 1979, ANN NY ACAD SCI, V328, P120, DOI 10.1111/j.1749-6632.1979.tb17773.x
[8]   Spanners of hypercube-derived networks [J].
Heydemann, MC ;
Peters, JG ;
Sotteau, D .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 1996, 9 (01) :37-54
[9]   A note on the ultimate categorical matching in a graph [J].
Hsu, LH .
DISCRETE MATHEMATICS, 2002, 256 (1-2) :487-488
[10]   Factoring cardinal product graphs in polynomial time [J].
Imrich, W .
DISCRETE MATHEMATICS, 1998, 192 (1-3) :119-144
123