Corrigendum to “Coined quantum walks lift the cospectrality of graphs and trees” [Pattern Recognition 42 (9) (2009) 1988–2002]by David Emms, Simone Severini, Richard C. Wilson, Edwin R. Hancock

Pattern Recognition

About

Year
2015
DOI
10.1016/j.patcog.2014.08.022
Subject
Artificial Intelligence / Computer Vision and Pattern Recognition / Signal Processing / Software

Text

Corrigendum

Corrigendum to “Coined quantum walks lift the cospectrality of graphs and trees” [Pattern Recognition 42 (9) (2009) 1988–2002]

David Emms a, Simone Severini b, Richard C. Wilson a, Edwin R. Hancock a,n a Department of Computer Science, University of York, York YO10 5DD, UK b Institute for Quantum Computing, Department of Combinatorics and Optimization, University of Waterloo, 2133 Davis Centre, Waterloo, Ontario,

Canada N2L 3G1

Independent verification showed that the entries in the last column of Table 4 in [1], giving the numbers of trees that have a cospectral partner with respect to the matrix Sþ ðU3Þ, were incorrect. The correct entries are given in Table 1.

Contents lists available at ScienceDirect journal homepage: www.elsevier.com/locate/pr

Pattern Recognition

Table 1

The number of trees on jV j vertices that have a cospectral partner with respect to the matrix Sþ ðU3Þ. jV j Number of trees Cospectral Sþ ðU3Þ r10 201 0 11 235 0 12 551 0 13 1301 0 14 3159 0 15 7741 0 16 19,320 0 17 48,629 0 18 123,867 0 19 317,955 0 20 823,065 0 21 2,144,505 0 22 5,623,756 0 23 14,828,074 0 24 39,299,897 2 25 104,636,890 0 26 279,793,450 0

Fig. 1. The unique pair of trees that are cospectral with respect to Sþ ðU3Þ among all trees with up to 26 vertices. http://dx.doi.org/10.1016/j.patcog.2014.08.022 0031-3203/& 2014 Elsevier Ltd. All rights reserved.

DOI of original article: http://dx.doi.org/10.1016/j.patcog.2008.10.025 n Corresponding author.

E-mail address: erh@cs.york.ac.uk (E.R. Hancock).

Pattern Recognition 48 (2015) 1574–1575

The errors occurred due to a failure of Lapack computational routines to converge for a small number of sparse matrices followed by a failure to trap the resulting error condition. Such trees were therefore reported as cospectral to each other.

The unique pair of trees on 24 vertices that are cospectral with respect to Sþ ðU3Þ is shown in Fig. 1.

Acknowledgment

The authors would like to thank Mohammad Ghebleh (Department of Mathematics, Kuwait University) and Dragan Stevanovic (Mathematical Institute, Serbian Academy of Science and Arts and University of Primorska, Institute Andrej Marusic, Slovenia) for helping identify the error and discussions surrounding the issues involved.

Reference [1] D. Emms, S. Severini, R.C. Wilson, E.R. Hancock, Coined quantum walks lift the cospectrality of graphs and trees, Pattern Recognit. 42 (2009) 1988–2002.

D. Emms et al. / Pattern Recognition 48 (2015) 1574–1575 1575