Pagenumber of complete bipartite graphs

Given an ordering of the vertices of a graph around a circle, a page is a collection of edges forming noncrossing chords. A book embedding is a circular permutation of the vertices together with a partition of the edges into pages. The pagenumber t(G) (also called book thickness) is the minimum number of pages in a book embedding of G. We present a general construction showing t(K_m,n) ? ?(m + 2n)/4?, which we conjecture optimal. We prove a result suggesting this is optimal for m ? 2n ? 3. For the most difficult case m = n, we consider vertex permutations that are regular, i.e., place vertices from each partite set into runs of equal size. Book embeddings with such orderings require ?(7n ? 2)/9? pages, which is achievable. The general construction uses fewer pages, but with an irregular ordering.     

Pagenumber of pathwidth-k graphs and strong pathwidth-k graphs

In this paper, it is shown that the maximum pagenumber of the graphs with pathwidth k is k and that the maximum pagenumber of the graphs with strong pathwidth k is in between ⌈3(k−1)/2⌉ and 3⌈k/2⌉.     

On Infinite Cycles I

We adapt the cycle space of a finite graph to locally finite infinite graphs, using as infinite cycles the homeomorphic images of the unit circle S¹ in the graph compactified by its ends. We prove that this cycle space consists of precisely the sets of edges that meet every finite cut evenly, and that the spanning trees whose fundamental cycles generate this cycle space are precisely the end-faithful spanning trees. We also generalize Eulers theorem by showing that a locally finite connected graph with ends contains a closed topological curve traversing every edge exactly once if and only if its entire edge set lies in this cycle space.To the memory of C. St. J. A. Nash-Williams     

On Infinite Cycles II

We adapt the cycle space of a finite or locally finite graph to graphs with vertices of infinite degree, using as cycles the homeomorphic images of the unit circle S¹ in the graph together with its ends. We characterize the spanning trees whose fundamental cycles generate this cycle space, and prove infinite analogues to the standard characterizations of finite cycle spaces in terms of edge-decomposition into single cycles and orthogonality to cuts.To the memory of C. St. J. A. Nash-Williams     

On Skubenko's Theorem on Cycles

In this paper, we give a new proof of the theorem due to B. F. Skubenko providing an estimate of the ratio between lengths of periods for two real quadratic irrationalities of the same discriminant. Bibliography: 9 titles.     

On the Limit Cycles of Quadratic Differential Systems

In this paper we give the necessary and sufficient conditions for all finite critical points of quadratic differential systems to be weak foci, and solve an open problem proposed by Yanquian Ye. Received January 11, 1999, Revised October 10, 2000, Accepted March 5, 2001     

On the Existence of Disjoint Cycles in a Graph

G is a graph of order at least 3k with . Then G contains k vertex-disjoint cycles. Received: April 23, 1998     

On Extremal Hypergraphs for Hamiltonian Cycles

We study sufficient conditions for Hamiltonian cycles in hypergraphs and obtain both Turán- and Dirac-type results. While the Turán-type result gives an exact threshold for the appearance of a Hamiltonian cycle in a hypergraph depending only on the extremal number of a certain path, the Dirac-type result yields just a sufficient condition relying solely on the minimum vertex degree.     

On Integral Graphs with Few Cycles

A graph is called integral if the spectrum of its adjacency matrix has only integer eigenvalues. In this paper, all integral graphs with at most two cycles (trees, unicyclic and bicyclic graphs) with no eigenvalue 0 are identified. Moreover, we give some results on unicyclic integral graphs with exactly one eigenvalue 0.     

On Cycles in 3-Connected Graphs

 Let G be a 3-connected graph of order n and S a subset of vertices. Denote by δ(S) the minimum degree (in G) of vertices of S. Then we prove that the circumference of G is at least min{|S|, 2δ(S)} if the degree sum of any four independent vertices of S is at least n+6. A cycle C is called S-maximum if there is no cycle C ^′ with |C ^′∩S|>|C∩S|. We also show that if ∑⁴ _i=1 d(a _i)≥n+3+|⋂⁴ _i=1 N(a _i)| for any four independent vertices a ₁, a ₂, a ₃, a ₄ in S, then G has an S-weak-dominating S-maximum cycle C, i.e. an S-maximum cycle such that every component in G−C contains at most one vertex in S. Received: March 9, 1998 Revised: January 7, 1999     

On Second Order Bifurcations of Limit Cycles

The paper derives a formula for the second variation of thedisplacement function for polynomial perturbations of Hamiltoniansystems with elliptic or hyperelliptic Hamiltonians H(x, y)=y²–U(x)in terms of the coefficients of the perturbation. As an application,the conjecture stated by C. Chicone that a specific cubic systemappearing in a deformation of singularity with two zero eigenvalueshas at most two limit cycles is proved.     

On the Oberwolfach Problem with Two Similar Length Cycles

 For all m≥3, the Oberwolfach problem is solved for the case where the 2-factors consist of two cycles of lengths m and m+1, and for the case where the 2-factors consist of two cycles of lengths m and m+2. Received: September 1, 1997 Final version received: August 10, 1999     

带弦圈的最小2宽直径

设k为正整数,G是简单k连通图.图G的k宽直径,dk(G),是指最小的整数ι使得对任意两不同顶点x,y∈V(G),都存在k条长至多为ι的内部不交的连接x和y的路.用C(n,t)表示在圈Gn上增加t条边所得的图.定义h(n,t):min{d2(C(n,t))}.本文给出了h(n,2)=[n/2].而且,给出了当t较大时h(n,t)的界.     

On the Detection of Limit Cycles by the Variational Velocity Method

This paper summarizes, clarifies, and corrects some aspects of the variational velocity methodfor the detection of limit cycles. After definitions and statements of the most important theoremsassociated with this method, some aspects of the proof of the main theorem are corrected andreworked. An example from the original paper in Acta Appl. Math. 48 (1997),13–32, is then discussed and criticized. Finally, the limitations of this method are discussed,especially as it applies to systems involving multiple limit cycles (and therefore as it applies toHilberts XVIth Problem).     

On Cycles on Compact Locally Symmetric Varieties

 We give a criterion to determine when the cycle class of a locally symmetric subvariety of a compact locally symmetric variety generates a non-trivial module under the action of Hecke operators, and give several examples where this criterion is satisfied. We also exhibit examples of subvarieties which do generate the trivial module under the action of Hecke operators. We show that all Hodge classes (in degree ) on the locally symmetric variety associated to certain arithmetric subgroups Γ of are algebraic (provided that ). Received 16 January 2001; in revised form 18 October 2001     

On Independent Cycles in a Bipartite Graph

 Let G=(V ₁,V ₂;E) be a bipartite graph with 2k≤m=|V ₁|≤|V ₂|=n, where k is a positive integer. We show that if the number of edges of G is at least (2k−1)(n−1)+m, then G contains k vertex-disjoint cycles, unless e(G)=(2k−1)(n−1)+m and G belongs to a known class of graphs. Received: December 9, 1998 Final version received: June 2, 1999     

图的一般邻点可区别均匀边染色和均匀全染色

提出了一般邻点可区别均匀边染色和全染色的新概念,研究了路P_n、圈C_n、星S_n、扇F_n、轮W_n、完全二部图K_(m,n)、2维平面网格图P_m×P_n的一般邻点可区别均匀边染色和全染色,具体给出这些图的一般邻点可区别均匀边染色和全染色指标.     

多部竞赛图中包含某条弧的圈

多部竞赛图或n部竞赛图是指一个完全n部无向图的定向图.2007年Volkmann证明了每个强连通的n部竞赛图(n≥3)至少存在一条弧它包含在从3到n的每个长度的圈中.在此基础上给出了强连通n部竞赛图中存在一条弧它包含在从3到n+1的每个长度的圈中的一个充分条件,并举例说明该条件在某种意义上的最佳可能性.     

On Edge-Colored Graphs Covered by Properly Colored Cycles

We characterize edge-colored graphs in which every edge belongs to some properly colored cycle. We obtain our result by applying a characterization of 1-extendable graphs. Received: April, 2003