Edge-isoperimetric problems for cartesian powers of regular graphs

被引：20

作者：

Bezrukov, SL ^{[1
]}

Elsässer, R

机构：

[1] Univ Wisconsin, Dept Math & Comp Sci, Superior, WI 54880 USA

[2] Univ Gesamthsch Paderborn, Dept Math & Comp Sci, D-33102 Paderborn, Germany

来源：

THEORETICAL COMPUTER SCIENCE | 2003年 / 307卷 / 03期

关键词：

edge-isoperimetric problem; isoperimetric inequality; regular graphs; cartesian product; lexicographic order;

D O I：

10.1016/S0304-3975(03)00232-9

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We consider an edge-isoperimetric problem (EIP) on the cartesian powers of graphs. One of our objectives is to extend the list of graphs for whose cartesian powers the lexicographic order provides nested solutions for the EIP. We present several new classes of such graphs that include as special cases all presently known graphs with this property. Our new results are applied to derive best possible edge-isoperimetric inequalities for the cartesian powers of arbitrary regular, resp. regular bipartite, graphs with a high density. (C) 2003 Elsevier B.V. All rights reserved.

引用

页码：473 / 492

页数：20

共 9 条

[1] General edge-isoperimetric inequalities .2. A local-global principle for lexicographical solutions [J].

Ahlswede, R ;

Cai, N .

EUROPEAN JOURNAL OF COMBINATORICS, 1997, 18 (05) :479-489

[2] EDGE ISOPERIMETRIC THEOREMS FOR INTEGER POINT ARRAYS [J].

AHLSWEDE, R ;

BEZRUKOV, SL .

APPLIED MATHEMATICS LETTERS, 1995, 8 (02) :75-80

[3]

Bezrukov S. L., 2000, ANN COMB, V4, P153, DOI DOI 10.1007/S000260050003

[4]

Bezrukov SL, 1999, BOLYAI MATH STUD, V7, P157

[5]

BEZRUKOV SL, 1988, P INT C ALG COMB COD, P12

[6] EDGE-ISOPERIMETRIC INEQUALITIES IN THE GRID [J].

BOLLOBAS, B ;

LEADER, I .

COMBINATORICA, 1991, 11 (04) :299-314

[7] The edge-isoperimetric problem for discrete tori [J].

Carlson, TA .

DISCRETE MATHEMATICS, 2002, 254 (1-3) :33-49

[8] OPTIMAL ASSIGNMENTS OF NUMBERS TO VERTICES [J].

HARPER, LH .

JOURNAL OF THE SOCIETY FOR INDUSTRIAL AND APPLIED MATHEMATICS, 1964, 12 (01) :131-135

[9] ASSIGNMENT OF NUMBERS TO VERTICES [J].

LINDSEY, JH .

AMERICAN MATHEMATICAL MONTHLY, 1964, 71 (05) :508-&

← 1 →