Long Cycles Generate the Cycle Space of a Graph

Let G be a 2-connected graph in which the degree of every vertex is at least d. We prove that the cycles of length at least d + 1 generate the cycle space of G, unless G ≌ K_d+1 and d is odd. As a corollary, we deduce that the cycles of length at least d + 1 generate the subspace of even cycles in G. We also establish the existence of odd cycles of length at least d + 1 in the case when G is not bipartite.A second result states: if G is 2-connected with chromatic number at least k, then the cycles of length at least k generate the cycle space of G, unless G ≌ K_k and k is even. Similar corollaries follow, among them a stronger version of a theorem of Erdös and Hajnal.     

On the Cycle Space of an Infinite 3-connected Graph

Problems related to Tutte’s theorem on the generation of the cycle space of a 3-connected finite graph are discussed for infinite graphs.     

5连通图中的可去边

An edge e of a k-connected graph G is said to be a removable edge if G O e is still k-connected, where G e denotes the graph obtained from G by deleting e to get G - e, and for any end vertex of e with degree k - 1 in G- e, say x, delete x, and then add edges between any pair of non-adjacent vertices in NG-e （x）. The existence of removable edges of k-connected graphs and some properties of 3-connected and 4-connected graphs have been investigated [1, 11, 14, 15]. In the present paper, we investigate some properties of 5-connected graphs and study the distribution of removable edges on a cycle and a spanning tree in a 5- connected graph. Based on the properties, we proved that for a 5-connected graph G of order at least 10, if the edge-vertex-atom of G contains at least three vertices, then G has at least （3│G│ ＋ 2）/2 removable edges.     

Estimate of the Number of Edges in Subgraphs of a Johnson Graph

Doklady Mathematics - New estimates for the minimum number of edges in subgraphs of a Johnson graph are obtained.     

一个六点七边图的填充与覆盖

$\lambda{K_v}$为$\lambda$重$v$点完全图, $G$ 为有限简单图. $\lambda {K_v}$ 的一个 $G$-设计 ( $G$-填充设计, $G$-覆盖设计), 记为 ($v,G,\lambda$)-$GD$(($v,G,\lambda$)-$PD$, ($v,G,\lambda$)-$CD$), 是指一个序偶($X,\calB$)，其中 $X$ 为 ${K_v}$ 的顶点集， $\cal B$ 为 ${K_v}$ 中同构于 $G$的子图的集合, 称为区组集,使得 ${K_v     

Maximum Number of Contractible Edges on Hamiltonian Cycles of a 3-Connected Graph

 We show that if G is a 3-connected hamiltonian graph of order at least 5, then there exists a hamiltonian cycle C of G such that the number of contractible edges of G which are on C is greater than or equal to . Received: July 31, 2000 Final version received: December 12, 2000 Acknowledgments. I would like to thank Professor Yoshimi Egawa for the help he gave to me during the preparation of this paper.     

Splitting Off Edges within a Specified Subset Preserving the Edge-Connectivity of the Graph

Splitting off a pair su, sv of edges in a graph G means the operation that deletes su and sv and adds a new edge uv. Given a graph G = (V + s, E) which is k-edge-connected (k ≥ 2) between vertices of V and a specified subset R  V, first we consider the problem of finding a longest possible sequence of disjoint pairs of edges sx, sy, (x ,y  R) which can be split off preserving k-edge-connectivity in V. If R = V and d(s) is even then a well-known theorem of Lovász asserts that a complete R-splitting exists, that is, all the edges connecting s to R can be split off in pairs. This is not the case in general. We characterize the graphs possessing a complete R-splitting and give a formula for the length of a longest R-splitting sequence. Motivated by the connection between splitting off results and connectivity augmentation problems we also investigate the following problem that we call the split completion problem: given G and R as above, find a smallest set F of new edges incident to s such that G′ = (V + s, E + F) has a complete R-splitting. We give a min-max formula for F as well as a polynomial algorithm to find a smallest F. As a corollary we show a polynomial algorithm which finds a solution of size at most k/2 + 1 more than the optimum for the following augmentation problem, raised in [[2]]: given a graph H = (V, E), an integer k ≥ 2, and a set R  V, find a smallest set F′ of new edges for which H′ = (V, E + F′) is k-edge-connected and no edge of F′ crosses R.     

Estimate of the Number of Edges in Special Subgraphs of a Distance Graph

Mathematical Notes - The classical problem of estimating the number of edges in a subgraph of a special distance graph is considered. Old results are significantly improved.     

Integer Points of Entire Functions

A result is proved which implies the following conjecture ofOsgood and Yang from 1976: if f and g are non-constant entirefunctions, such that T(r, f) = O(T(r,g)) as r and such thatg(z Z implies that f(z) Z, then there exists a polynomialG with coefficients in Q, such that G(Z) Z and f = G g. 2000Mathematics Subject Classification 30D20, 30D35.     

Action of a Graph Automorphism on the Space of Flows

Mathematical Notes -     

空间同宿环和异宿环的稳定性

关于平面同（异）宿环的稳定性已有不少文献讨论过，但关于空间同（异）宿环的稳定性尚没有任何结果．本文在可定义回复映射的条件下给出了同（异）宿环在其部分邻域中是渐近稳定的判据．这些结果在某种意义下是平面系统相应结果的推广，包括并推广了［２］，［３］的结果．本文最后讨论了Ｌｏｒｅｎｚ系统同宿环和三种群竞争系统异宿环的稳定性，所得结果和Ｓｐａｒｒｏｗ与Ｍａｙ等的数值结果相吻合．     

取整函数及其生成的数列

讨论三类整数列,这些数列的后项均是由前项与非整数乘积再取整后得到的,对应的取整函数分别为四舍五入取整函数、下取整函数、上取整函数．结果表明这三类整数列均为二阶线性递归数列．     

3-连通3-正则图生成树外的可去边

G是3-连通图，e是G中的一条边．若G-e是3-连通图的一个剖分，则称e是3-连通图的可去边．否则，e是G中不可去边．本给出3-连通3-正则图中生成树外可去边的分布情况及数目．     

Multiplication Operators Between the Lipschitz Space and the Space of Bounded Functions on a Tree

In this paper, we characterize the bounded and the compact multiplication operators between the space of bounded functions on the set of vertices of a rooted infinite tree T and the Banach space of complex-valued Lipschitz functions on T. We also determine the operator norm and the essential norm for the bounded multiplication operators between these spaces and show that there are no isometries among such operators.     

The Size of a Maximum Subgraph of the Random Graph with a Given Number of Edges

Doklady Mathematics - We have proven that the maximum size k of an induced subgraph of the binomial random graph $$G(n,p)$$ with a given number of edges $$e(k)$$ (under certain conditions on this...     

Subspace Inclusion Graph of a Vector Space

In this paper, the authors introduce a graph structure, called subspace inclusion graph ?n(𝕍) on a finite dimensional vector space 𝕍 where the vertex set is the collection of nontrivial proper subspaces of a vector space and two vertices are adjacent if one is contained in other. The diameter, girth, clique number, and chromatic number of ?n(𝕍) are studied. It is shown that two subspace inclusion graphs are isomorphic if and only if the base vector spaces are isomorphic. Finally, some properties of subspace inclusion graph are studied when the base field is finite.     

Representable Functions on the Unit Ball of a Banach Space

In this paper we treat the problem of integral representation of analytic functions over the unit ball of a complex Banach space X using the theory of abstract Wiener spaces. We define the class of representable functions on the unit ball of X and prove that this set of functions is related with the classes of integral k–homogeneous polynomials, integral holomorphic functions and also with the set of L ^p –representable functions on a Banach space.