On the canonical metric representation, average distance, and partial Hamming graphs

被引：53

作者：

Klavzar, S ^{[1
]}

机构：

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

来源：

EUROPEAN JOURNAL OF COMBINATORICS | 2006年 / 27卷 / 01期

关键词：

canonical metric representation; Hamming graphs; partial hamming graphs; Wiener index; recognition algorithm;

D O I：

10.1016/j.ejc.2004.07.008

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Average distance of a graph is expressed in terms of its canonical metric representation. The equality can be modified to an inequality in such a way that it characterizes isometric subgraphs of Hamming graphs. This approach simplifies recognition of these graphs and computation of their average distance. (c) 2004 Elsevier Ltd. All rights reserved.

引用

页码：68 / 73

页数：6

共 19 条

[1]

[Anonymous], 2000, DIMACS SER DISCRETE

[2]

Assouad P., 1980, Ann. Discrete Math, V8, P197, DOI [10.1016/S0167-5060(08)70874-4, DOI 10.1016/S0167-5060(08)70874-4]

[3] On the natural imprint function of a graph [J].

Bresar, B .

EUROPEAN JOURNAL OF COMBINATORICS, 2002, 23 (02) :149-161

[4] Partial Hamming graphs and expansion procedures [J].

Bresar, B .

DISCRETE MATHEMATICS, 2001, 237 (1-3) :13-27

[5] Fiber-complemented graphs - I: structure and invariant subgraphs [J].

Chastand, M .

DISCRETE MATHEMATICS, 2001, 226 (1-3) :107-141

[6] Clin d'oeil on L1-embeddable planar graphs [J].

Chepoi, V ;

Deza, M ;

Grishukhin, V .

DISCRETE APPLIED MATHEMATICS, 1997, 80 (01) :3-19

[7] ISOMETRIC SUBGRAPHS OF HAMMING GRAPHS AND D-CONVEXITY [J].

CHEPOI, VD .

CYBERNETICS, 1988, 24 (01) :6-11

[8] A note on l(1)-rigid planar graphs [J].

Deza, M ;

Tuma, J .

EUROPEAN JOURNAL OF COMBINATORICS, 1996, 17 (2-3) :157-160

[9] HYPERMETRIC GRAPHS [J].

DEZA, M ;

GRISHUKHIN, P .

QUARTERLY JOURNAL OF MATHEMATICS, 1993, 44 (176) :399-433

[10]

Deza MM, 1997, Math. Methods Oper. Res., V15, DOI 10.1007/978-3-642-04295-9

← 1 2 →