欧拉游历间K1—变换下的算法复杂性

本文主要讨论了欧拉图方面的国际权威ＨｅｒｂｅｒｔＦｌｅｉｃｈｎｅｒ教授所著书［１］中的一个问题；对欧拉图Ｇ的任意两个欧拉游历要经过多少Ｋ－变换或Ｋ＾＊－变换才能从一个游历得到另一个游历？我们得到的结论是：对欧拉图Ｇ中的任两个欧拉游历Ｔ、Ｔ＇最多经过‖Ｅ（Ｇ）‖－‖Ｖ（Ｇ）‖－变换可以使Ｔ变换成Ｔ＇。且此结果不能再改进。进一步我们分别对Ｋ－变换和Ｋ＆－变换的算法复杂性进行了讨论。     

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.