Strong isometric dimension, biclique coverings, and Sperner's theorem

被引：9

作者：

Froncek, Dalibor

Jerebic, Janja

Klavzar, Sandi

Kovar, Petr

机构：

[1] Univ Minnesota, Dept Math & Stat, Duluth, MN 55812 USA

[2] Univ Maribor, PeF, Dept Math & Comp Sci, SLO-2000 Maribor, Slovenia

[3] Tech Univ Ostrava, Dept Math & Descript Geometry, CS-70833 Ostrava, Czech Republic

来源：

COMBINATORICS PROBABILITY & COMPUTING | 2007年 / 16卷 / 02期

关键词：

D O I：

10.1017/S0963548306007711

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

The strong isometric dimension of a graph G is the least number k such that G isometrically embeds into the strong product of k paths. Using Sperner's theorem, the strong isometric dimension of the Hamming graphs K(2) square K(n) is determined.

引用

页码：271 / 275

页数：5

共 15 条

[1]

[Anonymous], PRODUCT GRAPHS STRUC

[2]

CHUNG FRK, 1981, SIAM J ALGEBRA DISCR, V2, P1, DOI 10.1137/0602001

[3] ON THE COVERINGS OF GRAPHS [J].

CHUNG, FRK .

DISCRETE MATHEMATICS, 1980, 30 (02) :89-93

[4]

DEWDNEY AK, 1980, ARS COMBINATORIA, V9, P77

[5]

ENGEL K, 1997, ENCY MATHH ITS APPL, V65

[6]

Fitzpatrick SL, 2001, ARS COMBINATORIA, V59, P65

[7]

Fitzpatrick SL., 2000, Discuss. Math. Graph Theory, V20, P23, DOI [10.7151/dmgt.1104, DOI 10.7151/DMGT.1104]

[8] Covering a graph with cuts of minimum total size [J].

Füredi, Z ;

Kündgen, A .

DISCRETE MATHEMATICS, 2001, 237 (1-3) :129-148

[9]

Isbell John R., 1964, Comment. Math. Helv, V39, P65, DOI DOI 10.1007/BF02566944

[10] On induced and isometric embeddings of graphs into the strong product of paths [J].

Jerebic, Janja ;

Klavzar, Sandi .

DISCRETE MATHEMATICS, 2006, 306 (13) :1358-1363

← 1 2 →