Sphere-of-influence graphs using the sup-norm

被引：7

作者：

Boyer, E ^{[1
]}

Lister, L

Shader, B

机构：

[1] Lyon Coll, Batesville, AR 72501 USA

[2] Bloomsburg Univ Penn, Bloomsburg, PA 17816 USA

[3] Univ Wyoming, Laramie, WY 82071 USA

来源：

MATHEMATICAL AND COMPUTER MODELLING | 2000年 / 32卷 / 10期

关键词：

sphere-of-influence; graphs; sup-metrix;

D O I：

10.1016/S0895-7177(00)00191-6

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

The SIG-dimension of sphere-of-influence graphs using the sup-norm is investigated. Constructions which give an upper bound on the SIG-dimension of arbitrary graphs are given. In addition, lower bounds, which are often tight, on the SIG-dimension of complete multipartite graphs are derived. (C) 2000 Elsevier Science Ltd. All rights reserved.

引用

页码：1071 / 1082

页数：12

共 14 条

[1]

Bondy J.A., 2008, GRAD TEXTS MATH

[2]

CVETKOVIC D, 1972, MAT VESNIK, V9, P141

[3]

Golumbic MC., 1980, Algorithmic Graph Theory and Perfect Graphs

[4]

GUIBAS L, 1991, INTUITIVE GEOMETRY, P131

[5] ABSTRACT SPHERE-OF-INFLUENCE GRAPHS [J].

HARARY, F ;

JACOBSON, MS ;

LIPMAN, MJ ;

MCMORRIS, FR .

MATHEMATICAL AND COMPUTER MODELLING, 1993, 17 (11) :77-83

[6]

Harary F., 1977, J GRAPH THEOR, V1, P131

[7]

KUBICKI G, ALL 2 CONNECTED OUTE

[8]

LIPMAN MJ, 1992, C NUMER, V91, P63

[9] SPHERE OF INFLUENCE GRAPHS - EDGE DENSITY AND CLIQUE SIZE [J].

MICHAEL, TS ;

QUINT, T .

MATHEMATICAL AND COMPUTER MODELLING, 1994, 20 (07) :19-24

[10]

MICHAEL TS, SPHERE INFLUENCE GRA

← 1 2 →