Eigenvalues of a graph and its imbeddings |
| |
Authors: | Michael Doob |
| |
Institution: | Department of Mathematics, University of Manitoba, Winnipeg, Manitoba, Canada |
| |
Abstract: | A graph H is imbedded in a graph G if a subset of the vertices of G determines a subgraph isomorphic to H. If λ(G) is the least eigenvalue of G and kR(H) = lim supd→∞ {λ(G)| H imbedded in G; G regular and connected; diam(G) > d; deg(G) > d}, then λ(H) ? 2 ≤ kR(H) ≤ λ(H) with these bounds being the best possible. Given a graph H, there exist arbitrarily large families of isospectral graphs such that H can be imbedded in each member of the family. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|