Ernesto Estrada and José A. de la Peña

Notes on Number Theory and Discrete Mathematics, ISSN 1310-5132

Volume 19, 2013, Number 3, Pages 78—84

**Download full paper: PDF, 168 Kb**

## Details

### Authors and affiliations

Ernesto Estrada

*Department of Mathematics and Statistics, University of Strathclyde
Glasgow G1 1XH, U.K.*

José A. de la Peña

*Centro de Investigación en Matemáticas (CIMAT)
A. C., Guanajuato 36240, México*

### Abstract

We define numbers of the type O_{j}(N) = N^{0} – N^{1} + N^{2} – … + N^{2j} and E^{j}(N) = –N^{0} + N^{1} – N^{2} + … + N^{2j+1} (j = 0, 1, 2, …) and the corresponding integer sequences. We prove that these integer sequences, e.g., S_{0}(N) = O_{0}(N), O_{1}(N), …, O_{r}(N), … and S_{E}(N) = E_{0}(N), E_{1}(N), …, E_{r}(N), … correspond to the number of odd and even walks in complete graphs KN. We then prove that there is a unique family of graphs which have exactly the same sequence of odd walks between connected nodes and of even walks between pairs of nodes at distance two, respectively. These graphs are the crown graphs: G_{2n} = K_{2} ⊗ K_{n}.

### Keywords

- Integer sequences
- Graph walks
- Crown graphs

### AMS Classification

- 05C50
- 11B99
- 05C76
- 05B05
- 05C81

### References

- Sloane, N. J. A. My favorite integer sequences.
*Sequences and Their Applications (Proceedings of SETA ’98)*, edited by C. Ding, T. Helleseth, and H. Niederreiter, Springer-Verlag, London, 1999, 103–130. - Sloane, N. J. A. The Online Encyclopedia of Integer Sequences.
*Notices of the ACM*, Vol. 50, 2003, 912–915. - The Online Encyclopedia of Integer Sequences. http://oeis.org/.
- Waller, D. A. Double covers of graphs,
*Bul. Austr. Math. Soc.*, Vol. 14, 1976, 233–248. - Haemers, W. H. Matrices for graphs, design and codes.
*Information Security, Coding Theory and Related Combinatorics*, D. Crnković and V. Tonchev (Eds.), IOS Press, 2011, 253–277. - Brouwer, A. E., A. M. Cohen, A. Neumaier,
*Distance Regular Graphs*. Springer- Verlag, Berlin, New York, 1989. - Cvetković, D. M., M. Doob, H. Sachs,
*Spectra of Graphs*, V.E.B. Deutscher Verlag der Wissenschaften, Berlin, 1979. - Fiol, M. A. Algebraic characterizations of distance-regular graphs.
*Discr. Math*., Vol. 246, 2002, 111–129. - Agarwal, S., P. K. Jha, M. Vikram, Distance regularity in direct-product graphs.
*Appl. Math. Lett.*, Vol. 13, 2000, 51–55.

## Related papers

## Cite this paper

APAEstrada, E., & De la Peña, J. A. (2013). Integer sequences from walks in graphs. Notes on Number Theory and Discrete Mathematics, 19(3), 78-84.

ChicagoEstrada, Ernesto, and José A. de la Peña. “Integer Sequences from Walks in Graphs.” Notes on Number Theory and Discrete Mathematics 19, no. 3 (2013): 78-84.

MLAEstrada, Ernesto, and José A. de la Peña. “Integer Sequences from Walks in Graphs.” Notes on Number Theory and Discrete Mathematics 19.3 (2013): 78-84.Print.