Addressing graph products and distance-regular graphs

被引：6

作者：

Cioaba, Sebastian M. ^{[1
]}

Elzinga, Randall J. ^{[2
,4
]}

Markiewitz, Michelle ^{[1
]}

Meulen, Kevin Vander ^{[3
]}

Vanderwoerd, Trevor ^{[3
,5
]}

机构：

[1] Univ Delaware, Dept Math Sci, Newark, DE 19716 USA

[2] Royal Mil Coll Canada, Dept Math, Kingston, ON K7K 7B4, Canada

[3] Redeemer Univ Coll, Dept Math, Ancaster, ON L9K 1J4, Canada

[4] Info Tech Res Grp, London, ON N6B 1Y8, Canada

[5] Univ Waterloo, Dept Civil & Environm Engn, Waterloo, ON N2L 3G1, Canada

来源：

DISCRETE APPLIED MATHEMATICS | 2017年 / 229卷

基金：

加拿大自然科学与工程研究理事会;

关键词：

Distance matrix; Spectrum; Triangular graphs; Hamming graphs; Graph addressing; BIPARTITE DECOMPOSITION; SPECTRUM;

D O I：

10.1016/j.dam.2017.05.018

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

Graham and Pollak showed that the vertices of any connected graph G can be assigned t-tuples with entries in {0, a, b}, called addresses, such that the distance in G between any two vertices equals the number of positions in their addresses where one of the addresses equals a and the other equals b. In this paper, we are interested in determining the minimum value of such t for various families of graphs. We develop two ways to obtain this value for the Hamming graphs and present a lower bound for the triangular graphs. (c) 2017 Elsevier B.V. All rights reserved.

引用

页码：46 / 54

页数：9

共 26 条

[1] More on the Bipartite Decomposition of Random Graphs [J].

Alon, Noga ;

Bohman, Tom ;

Huang, Hao .

JOURNAL OF GRAPH THEORY, 2017, 84 (01) :45-52

[2] Bipartite decomposition of random graphs [J].

Alon, Noga .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 2015, 113 :220-235

[3]

[Anonymous], 1973, ALGEBRAIC APPROACH A

[4] On the distance spectrum of distance regular graphs [J].

Atik, Fouzul ;

Panigrahi, Pratima .

LINEAR ALGEBRA AND ITS APPLICATIONS, 2015, 478 :256-273

[5]

BRANDENB.LH, 1972, AT&T TECH J, V51, P1445

[6]

Brouwer A.E., 2010, Spectra of Graphs

[7] DECOMPOSITION OF RANDOM GRAPHS INTO COMPLETE BIPARTITE GRAPHS [J].

Chung, Fan ;

Peng, Xing .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2016, 30 (01) :296-310

[8]

Cioaba S. M., 2002, THESIS

[9] Variations on a theme of Graham and Pollak [J].

Cioaba, Sebastian M. ;

Tait, Michael .

DISCRETE MATHEMATICS, 2013, 313 (05) :665-676

[10] Addressing the Petersen graph [J].

Elzinga, RJ ;

Gregory, DA ;

Vander Meulen, KN .

DISCRETE MATHEMATICS, 2004, 286 (03) :241-244

← 1 2 3 →