Topological studies on heteroconjugated molecules

A graph-theoretical analysis of certain -electron properties of alternant molecules with one heteroatom is given. Topological formulas for total -electron energy, -electron charge density, bond order and various polarizabilities are derived. The main results of the paper are summarized in Rules 1-7.     

Extended connectivity in chemical graphs

The true nature of the extended connectivity, used in Morgan algorithm for the canonical numerotation of points in chemical graphs, is discussed. An alternative method for its calculation based on the number of walks is described and shown to yield results identical to Morgan's method.     

Finding 2-edge connected spanning subgraphs

This paper studies the NP-hard problem of finding a minimum size 2-edge connected spanning subgraph (2-ECSS). An algorithm is given that on an r-edge connected input graph G=(V,E) finds a 2-ECSS of size at most |V|+(|E|−|V|)/(r−1). For r-regular, r-edge connected input graphs for r=3, 4, 5 and 6, this gives approximation guarantees of and , respectively.     

The dominating set problem is fixed parameter tractable for graphs of bounded genus

We describe an algorithm for the dominating set problem with time complexity O((4g+40)^kn²) for graphs of bounded genus g1, where k is the size of the set. It has previously been shown that this problem is fixed parameter tractable for planar graphs. We give a simpler proof for the previous O(8^kn²) result for planar graphs. Our method is a refinement of the earlier techniques.     

Entropy,Periodicity, and Graphs with Zero Euler Characteristic

Let G be a graph which contains exactly one simple closed curve. We prove that a continuous map f : G → G has zero topological entropy if and only if there exist at most k ≤ |(Edg(G) End(G) 3)/2] different odd numbers n1,...,nk such that Per(f) is contained in ∪i=1^k ∪j=0^∞ ni2^j, where Edg(G) is the number of edges of G and End(G) is the number of end points of G.     

Upper Bounds for the Laplacian Graph Eigenvalues

We first apply non-negative matrix theory to the matrix K = D A, where D and A are the degree-diagonal and adjacency matrices of a graph G, respectively, to establish a relation on the largest Laplacian eigenvalue λ1 (G) of G and the spectral radius p(K) of K. And then by using this relation we present two upper bounds for λ1(G) and determine the extremal graphs which achieve the upper bounds.     

On Integral Graphs Which Belong to the Class

Let G be a simple graph and let ¯G denote its complement. A graph G is said to be integral if its spectrum contains integral values. If is integral with >1 and a>b, where mG denotes the m-fold union of the graph G, we show that it belongs to the class of integral graphs where (i) (kn ² s ²+km nst+ms,km ² t ²+kmnst+ms)= such that (m,)=1 and (s,)=1; (ii) k,m,n,s,t,z such that (k,m)=1, (k,s)=1, (m,n)=1, (m,s)=1, (n,t)=1 and (s,t)=1; and (iii) ns>m t. Acknowledgments.The author is very grateful to the referees for their valuable comments and suggestions concerning this paper.1991 Mathematics Subject Classification. 05 C 50     

Chip firing and all-terminal network reliability bounds

The (all-terminal) reliability of a graph G is the probability that all vertices are in the same connected component, given that vertices are always operational but edges fail independently each with probability p. Computing reliability is #P-complete, and hence is expected to be intractable. Consequently techniques for efficiently (and effectively) bounding reliability have been the major thrust of research in the area. We utilize a deep connection between reliability and chip firings on graphs to improve previous bounds for reliability.     

微机Windows 9X平台上的分子模拟技术

通过例子介绍了微机Windows平台上的分子模拟技术——分子结构的生成、分子力学量子化学计算及计算结果的图形显示等内容。