Integer sequences from walks in graphs

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
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⁰ – N¹ + N² – … + N^2j and E^j(N) = –N⁰ + N¹ – N² + … + N^2j+1 (j = 0, 1, 2, …) and the corresponding integer sequences. We prove that these integer sequences, e.g., S₀(N) = O₀(N), O₁(N), …, O_r(N), … and S_E(N) = E₀(N), E₁(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₂ ⊗ K_n.

Keywords

• Integer sequences
• Graph walks
• Crown graphs

AMS Classification

• 05C50
• 11B99
• 05C76
• 05B05
• 05C81

References

1. 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.
2. Sloane, N. J. A. The Online Encyclopedia of Integer Sequences. Notices of the ACM, Vol. 50, 2003, 912–915.
3. The Online Encyclopedia of Integer Sequences. http://oeis.org/.
4. Waller, D. A. Double covers of graphs, Bul. Austr. Math. Soc., Vol. 14, 1976, 233–248.
5. 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.
6. Brouwer, A. E., A. M. Cohen, A. Neumaier, Distance Regular Graphs. Springer- Verlag, Berlin, New York, 1989.
7. Cvetković, D. M., M. Doob, H. Sachs, Spectra of Graphs, V.E.B. Deutscher Verlag der Wissenschaften, Berlin, 1979.
8. Fiol, M. A. Algebraic characterizations of distance-regular graphs. Discr. Math., Vol. 246, 2002, 111–129.
9. Agarwal, S., P. K. Jha, M. Vikram, Distance regularity in direct-product graphs. Appl. Math. Lett., Vol. 13, 2000, 51–55.