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
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 Oj(N) = N0 – N1 + N2 – … + N2j and Ej(N) = –N0 + N1 – N2 + … + N2j+1 (j = 0, 1, 2, …) and the corresponding integer sequences. We prove that these integer sequences, e.g., S0(N) = O0(N), O1(N), …, Or(N), … and SE(N) = E0(N), E1(N), …, Er(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: G2n = K2 ⊗ Kn.

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.

Related papers

Cite this paper

APA

Estrada, 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.

Chicago

Estrada, 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.

MLA

Estrada, 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.

Comments are closed.