Eigenvalues of neutral networks: interpolating between hypercubes

DOI10.1016/J.DISC.2015.11.011zbMATH Open1329.05197arXiv1504.03065OpenAlexW2594116931MaRDI QIDQ906473FDOQ906473

Authors: N. E. Zubov 

Publication date: 21 January 2016

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: A neutral network is a subgraph of a Hamming graph, and its principal eigenvalue determines its robustness: the ability of a population evolving on it to withstand errors. Here we consider the most robust small neutral networks: the graphs that interpolate pointwise between hypercube graphs of consecutive dimension (the point, line, line and point in the square, square, square and point in the cube, and so on). We prove that the principal eigenvalue of the adjacency matrix of these graphs is bounded by the logarithm of the number of vertices, and we conjecture an analogous result for Hamming graphs of alphabet size greater than two.

Full work available at URL: https://arxiv.org/abs/1504.03065

Recommendations

• Local connectivity of neutral networks
• scientific article; zbMATH DE number 874694
• Some new aspects of main eigenvalues of graphs
• Interconnection Networks and Their Eigenvalues
• Eigenvalues of subgraphs of the cube

zbMATH Keywords

evolvabilityhypercubegraph eigenvalueneutral networks

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Small world graphs, complex networks (graph-theoretic aspects) (05C82)

Cites Work

• Spectra of graphs
• Handbook of product graphs
• Cauchy's Interlace Theorem for Eigenvalues of Hermitian Matrices
• On the eigenvalues of trees
• Generalized Alon--Boppana Theorems and Error-Correcting Codes

Cited In (1)

• Eigenvalues of subgraphs of the cube

This page was built for publication: Eigenvalues of neutral networks: interpolating between hypercubes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q906473)