Hamiltonians on discrete structures: jumps of the integrated density of states and uniform convergence

We study equivariant families of discrete Hamiltonians on amenable geometries and their integrated density of states (IDS). We prove that the eigenspace of a fixed energy is spanned by eigenfunctions with compact support. The size of a jump of the IDS is consequently given by the equivariant dimension of the subspace spanned by such eigenfunctions. From this we deduce uniform convergence (w.r.t. the spectral parameter) of the finite volume approximants of the IDS. Our framework includes quasiperiodic operators on Delone sets, periodic and random operators on quasi-transitive graphs, and operators on percolation graphs.     

Further results on hierarchical product of graphs

The hierarchical product of graphs was introduced very recently by L. Barriére et al. in [L. Barriére, F. Comellas, C. Dafló and M. A. Fiol, On the spectra of hypertrees, Linear Algebra Appl. 428 (2008) 1499–1510]. In this paper, some properties of the hierarchical product, as well as its extension under Szeged, revised Szeged and edge Szeged indices of graphs are studied.     

Eigenfunction Expansions for Schrödinger Operators on Metric Graphs

We construct an expansion in generalized eigenfunctions for Schr?dinger operators on metric graphs. We require rather minimal assumptions concerning the graph structure and the boundary conditions at the vertices.      

Convex drawings of hierarchical planar graphs and clustered planar graphs

In this paper, we present results on convex drawings of hierarchical graphs and clustered graphs. A convex drawing is a planar straight-line drawing of a plane graph, where every facial cycle is drawn as a convex polygon. Hierarchical graphs and clustered graphs are useful graph models with structured relational information. Hierarchical graphs are graphs with layering structures; clustered graphs are graphs with recursive clustering structures.We first present the necessary and sufficient conditions for a hierarchical plane graph to admit a convex drawing. More specifically, we show that the necessary and sufficient conditions for a biconnected plane graph due to Thomassen [C. Thomassen, Plane representations of graphs, in: J.A. Bondy, U.S.R. Murty (Eds.), Progress in Graph Theory, Academic Press, 1984, pp. 43–69] remains valid for the case of a hierarchical plane graph. We then prove that every internally triconnected clustered plane graph with a completely connected clustering structure admits a “fully convex drawing,” a planar straight-line drawing such that both clusters and facial cycles are drawn as convex polygons. We also present algorithms to construct such convex drawings of hierarchical graphs and clustered graphs.     

On the Spectra of Certain Graphs Arising from Finite Fields

Cayley graphs on a subgroup ofGL(3,p),p>3 a prime, are defined and their properties, particularly their spectra, studied. It is shown that these graphs are connected, vertex-transitive, nonbipartite, and regular, and their degrees are computed. The eigenvalues of the corresponding adjacency matrices depend on the representations of the group of vertices. The “1-dimensional” eigenvalues can be completely described, while a portion of the “higher dimensional” eigenfunctions are discrete analogs of Bessel functions. A particular subset of these graphs is conjectured to be Ramanujan and this is verified for over 2000 graphs. These graphs follow a construction used by Terras on a subgroup ofGL(2,p). This method can be extended further to construct graphs using a subgroup ofGL(n, p) forn≥4. The 1-dimensional eigenvalues in this case can be expressed in terms of the 1-dimensional eigenvalues of graphs fromGL(2,p) andGL(3,p); this part of the spectra alone is sufficient to show that forn≥4, the graphs fromGL(n, p) are not in general Ramanujan.     

The hierarchical product of graphs

A new operation on graphs is introduced and some of its properties are studied. We call it hierarchical product, because of the strong (connectedness) hierarchy of the vertices in the resulting graphs. In fact, the obtained graphs turn out to be subgraphs of the cartesian product of the corresponding factors. Some well-known properties of the cartesian product, such as reduced mean distance and diameter, simple routing algorithms and some optimal communication protocols are inherited by the hierarchical product. We also address the study of some algebraic properties of the hierarchical product of two or more graphs. In particular, the spectrum of the binary hypertree T_m (which is the hierarchical product of several copies of the complete graph on two vertices) is fully characterized; turning out to be an interesting example of graph with all its eigenvalues distinct. Finally, some natural generalizations of the hierarchic product are proposed.     

Non-localization of eigenfunctions on large regular graphs

We give a delocalization estimate for eigenfunctions of the discrete Laplacian on large (d+1)-regular graphs, showing that any subset of the graph supporting ε of the L ² mass of an eigenfunction must be large. For graphs satisfying a mild girth-like condition, this bound will be exponential in the size of the graph.     

Matching shape graphs

Graphs are important structures to model complex relationships such as chemical compounds, proteins, geometric or hierarchical parts, and XML documents. Given a query graph, indexing has become a necessity to retrieve similar graphs quickly from large databases. We propose a novel technique for indexing databases, whose entries can be represented as graph structures. Our method starts by representing the topological structure of a graph as well as that of its subgraphs as vectors in which the components correspond to the sorted laplacian eigenvalues of the graph or subgraphs. By doing a nearest neighbor search around the query spectra, similar but not necessarily isomorphic graphs are retrieved. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

A Harnack inequality for Dirichlet eigenvalues

We prove a Harnack inequality for Dirichlet eigenfunctions of abelian homogeneous graphs and their convex subgraphs. We derive lower bounds for Dirichlet eigenvalues using the Harnack inequality. We also consider a randomization problem in connection with combinatorial games using Dirichlet eigenvalues. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 247–257, 2000     

阿贝尔齐性图上一种改进的关于Dirichlet特征值的Harnack型不等式

在本文中, 我们证明了在阿贝尔齐性图上一种改进的关于Dirichlet特征值的Harnack 型不等式,由此, 利用此Harnack 型不等式得到Dirichlet特征值的一个下界估计, 推广了 Chung 和 Yau 关于齐性图的一些结果.     

The generalized hierarchical product of graphs

A generalization of both the hierarchical product and the Cartesian product of graphs is introduced and some of its properties are studied. We call it the generalized hierarchical product. In fact, the obtained graphs turn out to be subgraphs of the Cartesian product of the corresponding factors. Thus, some well-known properties of this product, such as a good connectivity, reduced mean distance, radius and diameter, simple routing algorithms and some optimal communication protocols, are inherited by the generalized hierarchical product. Besides some of these properties, in this paper we study the spectrum, the existence of Hamiltonian cycles, the chromatic number and index, and the connectivity of the generalized hierarchical product.     

Dynamics of Nodal Points and the Nodal Count on a Family of Quantum Graphs

We investigate the properties of the zeros of the eigenfunctions on quantum graphs (metric graphs with a Schr?dinger-type differential operator). Using tools such as scattering approach and eigenvalue interlacing inequalities we derive several formulas relating the number of the zeros of the n-th eigenfunction to the spectrum of the graph and of some of its subgraphs. In a special case of the so-called dihedral graph we prove an explicit formula that only uses the lengths of the edges, entirely bypassing the information about the graph??s eigenvalues. The results are explained from the point of view of the dynamics of zeros of the solutions to the scattering problem.     

Parallel Algorithms for Hierarchical Clustering and Applications to Split Decomposition and Parity Graph Recognition

We present efficient (parallel) algorithms for two hierarchical clustering heuristics. We point out that these heuristics can also be applied to solving some algorithmic problems in graphs, including split decomposition. We show that efficient parallel split decomposition induces an efficient parallel parity graph recognition algorithm. This is a consequence of the result of S. Cicerone and D. Di Stefano [[7]] that parity graphs are exactly those graphs that can be split decomposed into cliques and bipartite graphs.     

Discrete spectra of the Dirac Hamiltonian in Coulomb and Aharonov-Bohm potentials in 2+1 dimensions

We find all self-adjoint Dirac Hamiltonians in Coulomb and Aharonov-Bohm potentials in 2+1 dimensions with the fermion spin taken into account. We obtain implicit equations for the spectra and construct eigenfunctions for all self-adjoint Dirac Hamiltonians in the indicated external fields. We find explicit solutions of the equations for the spectra in some cases.     

The degree sequences and spectra of scale‐free random graphs

We investigate the degree sequences of scale‐free random graphs. We obtain a formula for the limiting proportion of vertices with degree d, confirming non‐rigorous arguments of Dorogovtsev, Mendes, and Samukhin ( 14 ). We also consider a generalization of the model with more randomization, proving similar results. Finally, we use our results on the degree sequence to show that for certain values of parameters localized eigenfunctions of the adjacency matrix can be found. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

β−type fractional Sturm‐Liouville Coulomb operator and applied results

In this article, β‐type fractional Sturm‐Liouville Coulomb operator is considered by Hilfer fractional derivative. Fundamental spectral theory is investigated for the aforementioned problem. In this context, it is shown that the operator is self‐adjoint, eigenfunctions correspond to the distinct eigenfunctions are orthogonal, and eigenvalues are real. Furthermore, applications of this problem are given by the Adomian decomposition method and the results are shown with visual graphs.     

Asymptotics of the spectrum and eigenfunctions of the magnetic induction operator on a compact two-dimensional surface of revolution

Magnetic fields in conducting liquids (in particular, magnetic fields of galaxies, stars, and planets) are described by the magnetic induction operator. In this paper, we study the spectrum and eigenfunctions of this operator on a compact two-dimensional surface of revolution. For large magnetic Reynolds numbers, the asymptotics of the spectrum is studied; equations defining the eigenvalues (quantization conditions) are obtained; and examples of spectral graphs near which these points are located are given. The spatial structure of the eigenfunctions is studied.     

Pseudo-Differential Calculus on Homogeneous Trees

To study concentration and oscillation properties of eigenfunctions of the discrete Laplacian on regular graphs, we construct in this paper a pseudo-differential calculus on homogeneous trees, their universal covers. We define symbol classes and associated operators. We prove that these operators are bounded on L ² and give adjoint and product formulas. Finally, we compute the symbol of the commutator of a pseudo-differential operator with the Laplacian.