Graph Laplacians and topology

Laplace operators on metric graphs are considered. It is proven that for compact graphs the spectrum of the Laplace operator determines the total length, the number of connected components, and the Euler characteristic. For a class of non-compact graphs the same characteristics are determined by the scattering data consisting of the scattering matrix and the discrete eigenvalues.     

Bundles over Quantum Sphere and Noncommutative Index Theorem

The Noncommutative Index Theorem is used to prove that the Chern numbers of quantum Hopf line bundles over the standard Podle quantum sphere equal the winding numbers of the representations defining these bundles. This result gives an estimate of the positive cone of the algebraic K₀ of the standard quantum sphere.     

Eigenvalue Comparison Theorems of the Discrete Laplacians for a Graph

We give a graph theoretic analogue of Cheng's eigenvalue comparison theorems for the Laplacian of complete Riemannian manifolds. As its applications, we determine the infimum of the (essential) spectrum of the discrete Laplacian for infinite graphs.     

General Existence Theorem of Zero Points

Let X be a nonempty, compact, convex set in and let be an upper semicontinuous mapping from X to the collection of nonempty, compact, convex subsets of . It is well known that such a mapping has a stationary point on X; i.e., there exists a point X such that its image under has a nonempty intersection with the normal cone of X at the point. In the case where, for every point in X, it holds that the intersection of the image under with the normal cone of X at the point is either empty or contains the origin 0 ⁿ , then must have a zero point on X; i.e., there exists a point in X such that 0 ⁿ lies in the image of the point. Another well-known condition for the existence of a zero point follows from the Ky Fan coincidence theorem, which says that, if for every point the intersection of the image with the tangent cone of X at the point is nonempty, the mapping must have a zero point. In this paper, we extend all these existence results by giving a general zero-point existence theorem, of which the previous two results are obtained as special cases. We discuss also what kind of solutions may exist when no further conditions are stated on the mapping . Finally, we show how our results can be used to establish several new intersection results on a compact, convex set.     

Zero Divisor Graph of a Poset with Respect to an Ideal

In this paper, we introduce the zero divisor graph G _I (P) of a poset P (with 0) with respect to an ideal I. It is shown that G _I (P) is connected with its diameter ??3, and if G _I (P) contains a cycle, then the core K of G _I (P) is a union of 3-cycles and 4-cycles. Further, the chromatic number and clique number of G _I (P) are shown to be equal. This proves a form of Beck??s conjecture for posets with 0. The complete bipartite zero divisor graphs are characterized.     

A Zero Divisor Graph Determined by Equivalence Classes of Zero Divisors

We study the zero divisor graph determined by equivalence classes of zero divisors of a commutative Noetherian ring R. We demonstrate how to recover information about R from this structure. In particular, we determine how to identify associated primes from the graph.     

强完美图定理及相关的问题

介绍强完美图定理(The Strong Perfect Graph Theorem,SPGT)的历史和获证经过,同时简述SPGT被克服后生发的一些新问题,以期对图理论的一般研究起到鼓励和促进作用.因具体的证明浩大聱曲,在技术的部分仅注重框架而不涉及细节.     

A Cascadic Multigrid Algorithm for Computing the Fiedler Vector of Graph Laplacians

In this paper, we develop a cascadic multigrid algorithm for fast computation of the Fiedler vector of a graph Laplacian, namely, the eigenvector corresponding to the second smallest eigenvalue. This vector has been found to have applications in fields such as graph partitioning and graph drawing. The algorithm is a purely algebraic approach based on a heavy edge coarsening scheme and pointwise smoothing for refinement. To gain theoretical insight, we also consider the related cascadic multigrid method in the geometric setting for elliptic eigenvalue problems and show its uniform convergence under certain assumptions. Numerical tests are presented for computing the Fiedler vector of several practical graphs, and numerical results show the efficiency and optimality of our proposed cascadic multigrid algorithm.     

Operators with singular continuous spectrum, VI. Graph Laplacians and Laplace-Beltrami operators

Examples are constructed of Laplace-Beltrami operators and graph Laplacians with singular continuous spectrum.

     

Analytic Rank of Graph Algebras and Quantum Spaces

We show that the analytic rank, as defined by Murphy, of a unitalgraph C*-algebra is either 1 or 0, depending on whether or notthe underlying graph possesses an initial loop. As a corollary,we show that the analytic rank of certain quantum spaces (includingsome quantum spheres, projective spaces and lens spaces) is1. 2000 Mathematics Subject Classification 46L05, 46L65, 46L87.     

Edge-Distinguishing Index of a Graph

We introduce a concept of edge-distinguishing colourings of graphs. A closed neighbourhood of an edge \({e\in E(G)}\) is a subgraph N[e] induced by e and all edges adjacent to it. We say that a colouring c : E(G) → C does not distinguish two edges e ₁ and e ₂ if there exists an isomorphism φ of N[e ₁] onto N[e ₂] such that φ(e ₁) = e ₂ and φ preserves colours of c. An edge-distinguishing index of a graph G is the minimum number of colours in a proper colouring which distinguishes every two distinct edges of G. We determine the edge-distinguishing index for cycles, paths and complete graphs.     

On the Zero Modes of Weyl-Dirac Operators and Their Multiplicity

It is proved that the existence of zero modes of Weyl–Diracoperators is a rare phenomenon. An estimate of the multiplicityis given in term of the magnetic potential.     

探讨Abel积分零点的一个定理

本文研究了具有中心环域的可积多项式系统,探讨此系统在用多项式进行微扰的情况下,其所对应的Abel积分的零点个数的计算方法,给出了一个较为实用的定理,并举出了若干个应用的例子．     

Some Results on the Majorization Theorem of Connected Graph

Let π = (d1, d2, . . . , dn) and π'= (d1', d2' , . . . , d'n) be two non-increasing degree sequences. We say π is majorizated by π' , denoted by π△π , if and only if π≠π , Σni=1di=Σni=1d'i , and Σji=1di ≤Σji=1di for all j = 1, 2, . . . , n. We use Cπ to denote the class of connected graphs with degree sequence π. Let ρ(G) be the spectral radius, i.e., the largest eigenvalue of the adjacent matrix of G. In this paper, we extend the main results of [Liu, M. H., Liu, B. L., You, Z. F.: The majorization theorem of connected graphs. Linear Algebra Appl., 431(1), 553-557 (2009)] and [Biyikoglu, T., Leydold, J.: Graphs with given degree sequence and maximal spectral radius. Electron. J. Combin., 15(1), R119 (2008)]. Moreover, we prove that if π and π' are two different non-increasing degree sequences of unicyclic graphs with ππ' , G and G' are the unicyclic graphs with the greatest spectral radii in Cπ and Cπ' , respectively, then ρ(G) ρ(G').     

一个关于图谱的受控定理的推广

本文将一个关于两个不交国的单点粘合的图的LPlaCe谱的受控定理推广到了两个国的多点粘合何形；同时证明了相同的结果对目的Q一回也成立。     

速率函数零点定理的一个新证明

本文给出了速率函数零点定理的一种简捷证明方法．     

The Hamiltonian Index of a Graph

 It is proved that the hamiltonian index of a connected graph other than a path is less than its diameter which improves the results of P. A. Catlin etc. [J. Graph Theory 14 (1990) 347–364] and M. L. Sarazin [Discrete Math. 134(1994)85–91]. Nordhaus-Gaddum's inequalities for the hamiltonian index of a graph are also established. Received: July 17, 1998 Final version received: September 13, 1999