Addressing graph products and distance-regular graphs

DOI10.1016/J.DAM.2017.05.018MaRDI QIDQ2012052zbMATH OpenOpenAlexFDO

Authors Sebastian Cioaba, Randall J. Elzinga, Michelle Markiewitz, Kevin N. Vander Meulen, Trevor Vanderwoerd

Publication date 27 July 2017

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1609.05995

zbMATH Keywords

distance matrixspectrumHamming graphstriangular graphsgraph addressing

Mathematics Subject Classification ID

Distance in graphs (05C12) Connectivity (05C40) Structural characterization of families of graphs (05C75) Graph operations (line graphs, products, etc.) (05C76)

Abstract: 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.

Recommendations

• scientific article; zbMATH DE number 3920514
• Distance regularity in direct-product graphs
• Exact distance graphs of product graphs
• Products of distance degree regular and distance degree injective graphs
• Distance product of graphs
• scientific article; zbMATH DE number 4019107
• Distance preserving graphs and graph products.
• Distance two labelling and direct products of graphs
• scientific article; zbMATH DE number 4106886

Cites work

• scientific article; zbMATH DE number 1600999 (Why is no real title available?)
• scientific article; zbMATH DE number 5844218 (Why is no real title available?)
• scientific article; zbMATH DE number 790476 (Why is no real title available?)
• scientific article; zbMATH DE number 3395950 (Why is no real title available?)
• scientific article; zbMATH DE number 2232233 (Why is no real title available?)
• A \(q\)-analogue of the addressing problem of graphs by Graham and Pollak
• A course in combinatorics.
• Addressing the Petersen graph
• Biclique decompositions and Hermitian rank
• Bipartite decomposition of random graphs
• Decomposition of random graphs into complete bipartite graphs
• Depth-3 Arithmetic Circuits for S^2_n(X) and Extensions of the Graham-Pollack Theorem
• Distance spectrum of graph compositions
• Distance-regular graphs the distance matrix of which has only one positive eigenvalue
• Eigensharp Graphs: Decomposition into Complete Bipartite Subgraphs
• More on the bipartite decomposition of random graphs
• Nearly-neighborly families of tetrahedra and the decomposition of some multigraphs
• On the Addressing Problem for Loop Switching
• On the Addressing Problem of Loop Switching
• On the distance spectrum of distance regular graphs
• Proof of the squashed cube conjecture
• The Gewirtz graph: An exercise in the theory of graph spectra
• The inertia of distance matrices of some graphs
• Variations on a theme of Graham and Pollak

Cited in

(8)

• Wiener index and addressing of the total graph
• Addressing the Petersen graph
• scientific article; zbMATH DE number 3930895 (Why is no real title available?)
• The generalized distance spectrum of a graph and applications
• Eigenvalues of Cayley graphs
• On the addressing problem for directed graphs
• Addressing Johnson graphs, complete multipartite graphs, odd cycles, and random graphs
• scientific article; zbMATH DE number 5844218 (Why is no real title available?)

This page was built for publication: Addressing graph products and distance-regular graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2012052)