Counterexamples to the uniform shortest path routing conjecture for vertex-transitive graphs

被引：4

作者：

Shim, SH

Sirán, J ^{[1
]}

Zerovnik, J

机构：

[1] Pohang Univ Sci & Technol, Dept Math, Pohang 790784, South Korea

[2] Slovak Tech Univ Bratislava, Dept Math, Bratislava 81368, Slovakia

[3] Univ Maribor, FME, SLO-2000 Maribor, Slovenia

[4] IMFM, DTCS, Ljubljana, Slovenia

来源：

DISCRETE APPLIED MATHEMATICS | 2002年 / 119卷 / 03期

关键词：

routing; shortest path; vertex-transitive graph;

D O I：

10.1016/S0166-218X(01)00310-9

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

In this note we disprove the uniform shortest path routing conjecture for vertex-transitive graphs by constructing an infinite family of counterexamples. (C) 2002 Elsevier Science B.V. All rights reserved.

引用

页码：281 / 286

页数：6

共 10 条

[1]

[Anonymous], PRODUCT GRAPHS STRUC

[2] FORWARDING INDEX OF COMMUNICATION NETWORKS. [J].

Chung, Fan R.K. ;

Coffman Jr., Edward G. ;

Reiman, Martin I. ;

Simon, Burton .

IEEE Transactions on Information Theory, 1987, IT-33 (02) :224-232

[3] GROUPS OF GENERALIZED PETERSEN GRAPHS [J].

FRUCHT, R ;

GRAVER, JE ;

WATKINS, ME .

PROCEEDINGS OF THE CAMBRIDGE PHILOSOPHICAL SOCIETY-MATHEMATICAL AND PHYSICAL SCIENCES, 1971, 70 (SEP) :211-&

[4] On quasi-Cayley graphs [J].

Gauyacq, G .

DISCRETE APPLIED MATHEMATICS, 1997, 77 (01) :43-58

[5] FORWARDING INDEXES OF CONSISTENT ROUTINGS AND THEIR COMPLEXITY [J].

HEYDEMANN, MC ;

MEYER, JC ;

SOTTEAU, D ;

OPATRNY, J .

NETWORKS, 1994, 24 (02) :75-82

[6] ON FORWARDING INDEXES OF NETWORKS [J].

HEYDEMANN, MC ;

MEYER, JC ;

SOTTEAU, D .

DISCRETE APPLIED MATHEMATICS, 1989, 23 (02) :103-123

[7]

Heydemann MC, 1997, NATO ADV SCI I C-MAT, V497, P167

[8]

McKay BD, 1996, J GRAPH THEOR, V22, P321, DOI 10.1002/(SICI)1097-0118(199608)22:4<321::AID-JGT6>3.3.CO

[9]

2-9

[10] VERTEX-TRANSITIVE GRAPHS WHICH ARE NOT CAYLEY-GRAPHS .1. [J].

MCKAY, BD ;

PRAEGER, CE .

JOURNAL OF THE AUSTRALIAN MATHEMATICAL SOCIETY SERIES A-PURE MATHEMATICS AND STATISTICS, 1994, 56 :53-63

← 1 →