The generalized distance spectrum of a graph and applications

References

• Brouwer AE, Haemers WH. Spectra of graphs. New York: Universitext. Springer; 2012.
   Google Scholar
• Aouchiche M, Hansen P. Distance spectra of graphs: a survey.  Its Applications Linear Algebra Appl. 2014;458:301–386.
   Web of Science ®Google Scholar
• Atik F, Panigrahi P. On the distance spectrum of distance regular graphs.  Its Applications Linear Algebra Appl. 2015;478:256–273.
   Web of Science ®Google Scholar
• Edelberg M, Garey MR, Graham Ronald L. On the distance matrix of a tree. Discrete Math. 1976;14(1):23–39.
   Web of Science ®Google Scholar
• Graham RL, Lovász L. Distance matrix polynomials of trees. Adv Math (N Y). 1978;29(1):60–88.
   Web of Science ®Google Scholar
• Chung FRK. Spectral Graph Theory, Published for the Conference Board of the Mathematical Sciences, Washington, DC, by the American Mathematical Society; Providence, RI, 1997. (CBMS Regional Conference Series in Mathematics; 92).
   Google Scholar
• Brouwer AE, Cohen AM, Neumaier A. Distance-regular graphs, Berlin: Springer-Verlag; 1989. (Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)]; 18).
   Google Scholar
• Koolen JH, Shpectorov SV. Distance-regular graphs the distance matrix of which has only one positive eigenvalue. Eur J Combin. 1994;15(3):269–275.
   Web of Science ®Google Scholar
• van Dam ER, Haemers WH. Spectral characterizations of some distance-regular graphs. J Algebraic Combin. 2002;15(2):189–202.
   Web of Science ®Google Scholar
• van Dam ER, Koolen JH, Tanaka H. Distance-regular graphs. arXiv preprint arXiv:1410.6294v2, 2016
   Google Scholar
• Godsil C, Royle G. Algebraic graph theory. New York: Springer-Verlag; 2001. (Graduate texts in mathematics; 207)
   Google Scholar
• Aalipour G, Abiad A, Berikkyzy Z, et al. On the distance spectra of graphs.  Its Applications Linear Algebra Appl. 2016;497:66–87.
   Web of Science ®Google Scholar
• Azarija J. A short note on a short remark of Graham and Lovász. Discrete Math. 2014;315:65–68.
   Web of Science ®Google Scholar
• Barik S, Bapat RB, Pati S. On the Laplacian spectra of product graphs. Appl Anal Discrete Math. 2015;9(1):39–58.
   Google Scholar
• Indulal G, Gutman I. On the distance spectra of some graphs. Math Commun. 2008;13(1):123–131.
   Web of Science ®Google Scholar
• Lin H, Hong Y, Wang J, et al. On the distance spectrum of graphs.  Its Applications Linear Algebra Appl. 2013;439(6):1662–1669.
   Web of Science ®Google Scholar
• Ruzieh SN, Powers DL. The distance spectrum of the path Pn and the first distance eigenvector of connected graphs. Linear Multi Algebra. 1990;28(1-2):75–81.
   Google Scholar
• Graham RL, Pollak HO. On the addressing problem for loop switching. Bell Syst Tech J. 1971;50(8):2495–2519.
   Google Scholar
• Alon N, Cioabă SM, Gilbert BD. Addressing Johnson graphs, complete multipartite graphs, odd cycles, and random graphs. Exp Math. 2019: 1–11. DOI:10.1080/10586458.2018.1542643.
   Web of Science ®Google Scholar
• Cioabă SM, Elzinga RJ, Markiewitz M, et al. Addressing graph products and distance-regular graphs. Discrete Appl Math. 2017;229:46–54.
   Web of Science ®Google Scholar
• Elzinga RJ, Gregory DA, Vander Meulen KN. Addressing the Petersen graph.  Mathematics Discrete Math. 2004;286(3):241–244.
   Web of Science ®Google Scholar
• Fujii H, Sawa M. An addressing scheme on complete bipartite graphs. ARS Comb-Waterloo Winnipeg-. 2008;86:363.
   Web of Science ®Google Scholar
• Graham RL, Pollak HO. On embedding graphs in squashed cubes. In Graph theory and applications. Proceedings of the Conference at Western Michigan University, May 10 – 13, 1972.  Springer; 1972. p 99–110.
   Google Scholar
• Kratzke T, Reznick B, West D. Eigensharp graphs: decomposition into complete bipartite subgraphs.  Mathematical Society Trans Am Math Soc. 1988;308(2):637–653.
   Web of Science ®Google Scholar
• Watanabe S, Ishii K, Sawa M. A q-analogue of the addressing problem of graphs by graham and pollak. SIAM J Discrete Math. 2012;26(2):527–536.
   Web of Science ®Google Scholar
• Stevanović D. Distance regularity of compositions of graphs. Appl Math Lett. 2004;17(3):337–343.
   Web of Science ®Google Scholar
• Aggarwal S, Jha PK, Vikram M. Distance regularity in direct-product graphs. Appl Math Lett. 2000;13(1):51–55.
   Web of Science ®Google Scholar
• Song S-Y. Products of distance-regular graphs. Util Math. 1986;29:173–175.
   Web of Science ®Google Scholar
• Stevanović D, Indulal G. The distance spectrum and energy of the compositions of regular graphs. Appl Math Lett. 2009;22(7):1136–1140.
   Web of Science ®Google Scholar
• Indulal G. Distance spectrum of graph compositions. Ars Math Contemp. 2009;2:93–100.
   Web of Science ®Google Scholar
• Blasiak P, Flajolet P. Combinatorial models of Creation-annihilation. Séminaire Lotharingien de Combin. 2011;65(B65c):1–78.
   Google Scholar
• Cichacz S, Froncek D, Krop E, et al. Distance Magic Cartesian Products of Graphs. Discussiones Math Graph Theory. 2016;36(2):299–308.
   Web of Science ®Google Scholar
• Ito T, Terwilliger P. Distance-regular graphs and the q-tetrahedron algebra. Eur J Combin. 2009;30(3):682–697.
   Web of Science ®Google Scholar
• Horn RA, Johnson CR. Matrix analysis. 2nd ed.. Cambridge: Cambridge University Press; 2013.
   Google Scholar
• Weichsel PM. On distance-regularity in graphs. J Combin Theory, Ser B. 1982;32(2):156–161.
   Web of Science ®Google Scholar
• Reddy AS, Mehta SK. Pattern polynomial graphs. arXiv preprint arXiv:1106.4745, 2011
   Google Scholar
• Balasubramanian K. Computer generation of distance polynomials of graphs. J Comput Chem. 1990;11(7):829–836.
   Web of Science ®Google Scholar
• Balasubramanian K. A topological analysis of the c60 buckminsterfullerene and c70 based on distance matrices.  Physics Letters Chem Phys Lett. 1995;239(1-3):117–123.
   Web of Science ®Google Scholar
• Bapat R, Kirkland SJ, Neumann M. On distance matrices and laplacians.  Algebra and Its Applications Linear Algebra Appl. 2005;401:193–209.
   Web of Science ®Google Scholar
• Bose SS, Nath M, Paul S. Distance spectral radius of graphs with r pendent vertices.  Algebra and Its Applications Linear Algebra Appl. 2011;435(11):2828–2836.
   Web of Science ®Google Scholar
• Graovac A, Jashari G, Strunje M. On the distance spectrum of a cycle. Aplikace Matematiky. 1985;30(4):286–290.
   Google Scholar
• Merris R. The distance spectrum of a tree. J Graph Theory. 1990;14(3):365–369.
   Web of Science ®Google Scholar
• Xiao W, Gutman I. Resistance distance and laplacian spectrum. Theor Chem Acc. 2003;110(4):284–289.
   Web of Science ®Google Scholar
• Deza MM, Laurent M. Geometry of cuts and metrics. Vol. 15. Berlin, Heidelberg: Springer-Verlag; 2009.
   Google Scholar
• Lee G-S, Weng C-w.. A characterization of bipartite distance-regular graphs.  Its Applications Linear Algebra Appl. 2014;446:91–103.
   Web of Science ®Google Scholar
• Crow JF, Kimura M, eds. An introduction to population genetics theory. New York, Evanston and London: Harper & Row, Publishers; 1970.
   Google Scholar
• Domingo E, Schuster P. Quasispecies: from theory to experimental systems. Vol. 392. Switzerland: Springer International Publishing; 2016. DOI:10.1007/978-3-319-23898-2.
   Google Scholar
• Malarz K, Tiggemann D. Dynamics in eigen quasispecies model. Int J Modern Phys C. 1998;9(03):481–490.
   Google Scholar
• Roughgarden J. Theory of population genetics and evolutionary ecology: an introduction. New York, NY: Macmillan; 1979.
   Google Scholar
• Sigmund K, Hofbauer J. 1998. The theory of evolution and dynamical systems. Cambridge (UK): London Mathematical Society Student Texts; 7.
   Google Scholar
• Pianka ER. Evolutionary ecology. Harper and Row: New York; 1974.
   Google Scholar
• Schoener TW. Alternatives to Lotka-Volterra competition: models of intermediate complexity. Theor Popul Biol. 1976;10(3):309–333.
   PubMed Web of Science ®Google Scholar
• Turchin P. Complex population dynamics: a theoretical/empirical synthesis. Vol. 35Princeton University Press; 2003. https://press.princeton.edu/books/paperback/9780691090214/complex-population-dynamics.
   Google Scholar
• Page KM, Nowak MA. Unifying evolutionary dynamics. J Theor Biol. 2002;219(1):93–98.
   PubMed Web of Science ®Google Scholar
• Takeuchi Y. Global dynamical properties of Lotka-Volterra systems. Singapore: World Scientific; 1996.
   Google Scholar
• Macarthur R, Levins R. The limiting similarity, convergence, and divergence of coexisting species. Am Nat. 1967;101(921):377–385.
   Web of Science ®Google Scholar
• Doebeli M, Dieckmann U. Evolutionary branching and sympatric speciation caused by different types of ecological interactions. Am Nat. 2000;156(S4):S77–S101.
   PubMedGoogle Scholar
• Fort H, Inchausti P. Biodiversity patterns from an individual-based competition model on niche and physical spaces. J Stat Mech: Theory Exp. 2012;2012(02):P02013.
   Google Scholar
• Fort H, Scheffer M, van Nes EH. The paradox of the clumps, mathematically explained. Theor Ecol. 2009;2(3):171–176.
   Web of Science ®Google Scholar
• Fort H, Scheffer M, van Nes EH. The clumping transition in niche competition: a robust critical phenomenon. J Stat Mech: Theory Exp. 2010;2010(05):P05005.
   Google Scholar
• Galluccio S. Exact solution of the quasispecies model in a sharply peaked fitness landscape. Phys Rev E. 1997;56(4):4526.
   Web of Science ®Google Scholar
• Lawson DJ, Jensen HJ. Neutral evolution in a biological population as diffusion in phenotype space: reproduction with local mutation but without selection. Phys Rev Lett. 2007;98(9):098102.
   Google Scholar
• Park J-M, Muñoz E, Deem MW. Quasispecies theory for finite populations. Phys Rev E. 2010;81(1):011902.
   Google Scholar
• Pigolotti S, López C, Hernández-García E. Species clustering in competitive lotka-volterra models. Phys Rev Lett. 2007;98(25):258101.
   Google Scholar
• Pigolotti S, López C, Hernández-García E, et al. How Gaussian competition leads to lumpy or uniform species distributions. Theor Ecol. 2010;3(2):89–96.
   Web of Science ®Google Scholar
• Scheffer M, van Nes EH. Self-organized similarity, the evolutionary emergence of groups of similar species. Proc Natl Acad Sci. 2006;103(16):6230–6235.
   PubMed Web of Science ®Google Scholar
• Altmeyer S, McCaskill JS. Error threshold for spatially resolved evolution in the quasispecies model. Phys Rev Lett. 2001;86(25):5819.
   PubMed Web of Science ®Google Scholar
• Biancalani T, DeVille L, Goldenfeld N. Framework for analyzing ecological trait-based models in multidimensional niche spaces. Phys Rev E. 2015;91(5):052107.
   Google Scholar
• Rogers T, McKane AJ, Rossberg AG. Spontaneous genetic clustering in populations of competing organisms. Phys Biol. 2012;9(6):066002.
   Google Scholar
• Saakian DB, Ghazaryan M, Bratus A, et al. Biological evolution model with conditional mutation rates. Phys A: Stat Mech Appl. 2017;474:32–38.
   Google Scholar
• Semenov YS, Novozhilov AS. Generalized quasispecies model on finite metric spaces: Isometry groups and spectral properties of evolutionary matrices. arXiv preprint arXiv:1706.04253, 2017
   Google Scholar
• Lovász L. Random walks on graphs. Combin, Paul Erds Eighty. 1993;2:1–46.
   Google Scholar
• Norris JR. Markov chains. Cambridge: Cambridge University Press; 1998. (Cambridge Series in Statistical and Probabilistic Mathematics; 2). Reprint of 1997 original.
   Google Scholar
• Avin C, Krishnamachari B. The power of choice in random walks: an empirical study. Comput Netw. 2008;52(1):44–60.
   Web of Science ®Google Scholar
• Beraldi R. Random walk with long jumps for wireless ad hoc networks. Ad Hoc Netw. 2009;7(2):294–306.
   Web of Science ®Google Scholar
• Günes M, Spaniol O. Routing algorithms for mobile multi-hop ad-hoc networks. In International Workshop on Next Generation Network Technologies, 2002. p. 10–24.
   Google Scholar
• Shakkottai S. Asymptotics of search strategies over a sensor network. IEEE Trans Automat Contr. 2005;50(5):594–606.
   Web of Science ®Google Scholar
• Durrett R, Kesten H, Limic V. Once edge-reinforced random walk on a tree. Probab Theory Relat Fields. 2002;122(4):567–592.
   Web of Science ®Google Scholar
• Holmes M, Sakai A. Senile reinforced random walks.  Their Applications Stoch Process Their Appl. 2007;117(10):1519–1539.
   Web of Science ®Google Scholar
• Boyd S, Diaconis P, Xiao L. Fastest mixing Markov chain on a graph. SIAM Rev. 2004;46(4):667–689.
   Web of Science ®Google Scholar
• Carli R, Fagnani F, Speranzon A, et al. Communication constraints in the average consensus problem. Automatica. 2008;44(3):671–684.
   Web of Science ®Google Scholar
• Dyer M, Greenhill C. A more rapidly mixing Markov chain for graph colorings. Random Struct Algorithms. 1998;13(3-4):285–317.
   Web of Science ®Google Scholar
• Sinclair A, Jerrum M. Approximate counting, uniform generation and rapidly mixing markov chains. Inform Comput. 1989;82(1):93–133.
   Web of Science ®Google Scholar
• Boyd S, Diaconis P, Parrilo P, et al. Fastest mixing Markov chain on graphs with symmetries. SIAM J Optim. 2009;20(2):792–819.
   Web of Science ®Google Scholar
• Levin DA, Peres Y, Wilmer EL. Markov chains and mixing times. Providence, RI: American Mathematical Society; 2009. With a chapter by James G. Propp and David B. Wilson.
   Google Scholar
• Bubley R, Dyer M. Path coupling: A technique for proving rapid mixing in Markov chains. In Proceedings of the 38th Annual Symposium on Foundations of Computer Science, Miami Beach, FL, USA,1997, IEEE; 1997. p. 223–231.
   Google Scholar
• Chen G-Y, Saloff-Coste L. On the mixing time and spectral gap for birth and death chains. arXiv preprint arXiv:1304.4346, 2013
   Google Scholar
• Goel S, Montenegro R, Tetali P. Mixing time bounds via the spectral profile. Electronic J Probab. 2006;11:1–26.
   Web of Science ®Google Scholar
• Montenegro R, Tetali P, Mathematical aspects of mixing times in markov chains. Found Trends Theoretical Comput Sci. 2006;1(3):237–354.
   Google Scholar
• Morris B, Peres Y. Evolving sets, mixing and heat kernel bounds. Probab Theory Relat Fields. 2005;133(2):245–266.
   Web of Science ®Google Scholar
• Hilano T, Nomura K. Distance degree regular graphs. J Comb Theory, Seri B. 1984;37(1):96–100.
   Web of Science ®Google Scholar
• Boyd S, Vandenberghe L. Convex Optimization. Cambridge (UK): Cambridge University Press; 2004.
   Google Scholar
• Biggs N. Algebraic graph theory. London: Cambridge University Press; 1974. (Cambridge tracts in mathematics; 67).
   Google Scholar
• Seidel JJ. Strongly regular graphs with (−1,1,0) adjacency matrix having eigenvalue 3.  Algebra and Its Applications Linear Algebra Appl. 1968;1(2):281–298.
   Google Scholar
• Filmus Y. Orthogonal basis for functions over a slice of the Boolean hypercube. arXiv e-prints, arXiv:1406.0142, June 2014
   Google Scholar
• Koolen JH, Markowsky G, Park J. On electric resistances for distance-regular graphs. Eur J Combin. 2013;34(4):770–786.
   Web of Science ®Google Scholar
• Markowsky G, Koolen J. A conjecture of Biggs concerning the resistance of a distance-regular graph. Electron J Combina. 2010;17(1):R78.
   Web of Science ®Google Scholar