Addressing graph products and distance-regular graphs

DOI10.1016/J.DAM.2017.05.018zbMATH Open1367.05176arXiv1609.05995OpenAlexW2963479788MaRDI QIDQ2012052FDOQ2012052

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)

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.

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

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

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)

Cites Work

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

Cited In (8)

• Wiener index and addressing of the total graph
• Addressing the Petersen graph
• Title not available (Why is that?)
• The generalized distance spectrum of a graph and applications
• Eigenvalues of Cayley graphs
• Addressing Johnson graphs, complete multipartite graphs, odd cycles, and random graphs
• On the addressing problem for directed graphs
• Title not available (Why is that?)

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)