Addressing the Petersen graph
| Autor: | David A. Gregory, Randall J. Elzinga, Kevin N. Vander Meulen |
|---|---|
| Rok vydání: | 2004 |
| Předmět: |
Distance matrix
Discrete mathematics Graph center Graph labeling Applied Mathematics 010102 general mathematics Voltage graph Eigenvalues Generalized Petersen graph 0102 computer and information sciences Addressing 01 natural sciences Distance-regular graph Theoretical Computer Science Combinatorics 010201 computation theory & mathematics Graph power Petersen family Petersen graph Discrete Mathematics and Combinatorics 0101 mathematics Mathematics Toroidal graph |
| Zdroj: | Discrete Mathematics. 286:241-244 |
| ISSN: | 0012-365X |
| DOI: | 10.1016/j.disc.2004.06.006 |
| Popis: | Motivated by a problem on message routing in communication networks, Graham and Pollak proposed a scheme for addressing the vertices of a graph G by N-tuples of three symbols in such a way that distances between vertices may readily be determined from their addresses. They observed that Nh(D), the maximum of the number of positive and the number of negative eigenvalues of the distance matrix D of G. A result of Gregory, Shader and Watts yields a necessary condition for equality to occur. As an illustration, we show that N > h(D)= 5 for all addressings of the Petersen graph and then give an optimal addressing by 6-tuples. © 2004 Elsevier B.V. All rights reserved. MSC: 05C50; 05C20 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect