Cubical 4-Polytopes with Few Vertices

A cubical polytope is a convex polytope all of whose facets are conbinatorial cubes. A d-polytope Pis called almost simple if, in the graph of P, each vertex of Pis d-valent of (d+ 1)-valent. It is known that, for d> 4, all but one cubical d-polytopes with up to 2^d+1vertices are almost simple, which provides a complete enumeration of all the cubical d-polytopes with up to 2^d+1vertices. We show that this result is also true for d=4.     

On the Asymmetry Constant of a Body with Few Vertices

In this note, we show that a nondegenerated polytope in IR ⁿ with n + k, 1 k < n, vertices is far from any symmetric body. We provide the asymptotically sharp estimates for the asymmetry constant of such polytopes.     

任意长圈覆盖指定的独立的点

An invariant σ2（G） of a graph is defined as follows： σ2（G） ：= min{d（u） ＋ d（v）｜u, v ∈V（G）,uv ∈ E（G）,u ≠ v} is the minimum degree sum of nonadjacent vertices （when G is a complete graph, we define σ2（G） = ∞）. Let k, s be integers with k ≥ 2 and s ≥ 4, G be a graph of order n sufficiently large compared with s and k. We show that if σ2（G） ≥ n ＋ k- 1, then for any set of k independent vertices v1,..., vk, G has k vertex-disjoint cycles C1,..., Ck such that ｜Ci｜ ≤ s and vi ∈ V（Ci） for all 1 ≤ i ≤ k.
The condition of degree sum σs（G） ≥ n ＋ k - 1 is sharp.     

Geometric Realisations of Cubical Sets with Connections, and Classifying Spaces of Categories

We investigate the category of cubical sets with some additional degeneracies called connections. We prove that the realisation of a cubical set with connections is independent, up to homotopy, of whether we collapse those extra degeneracies or not and that any cubical set which is Kan admits connections. Using this type of cubical sets we define the cubical classifying space of a category and prove that this is equivalent to the simplicial one.     

Spanning Trees with Few Leaves

In this paper, we prove that an m-connected graph G on n vertices has a spanning tree with at most k leaves (for k ≥ 2 and m ≥ 1) if every independent set of G with cardinality m + k contains at least one pair of vertices with degree sum at least n − k + 1. This is a common generalization of results due to Broersma and Tuinstra and to Win.     

Hamiltonicity and Degrees of Adjacent Vertices in Claw‐Free Graphs

For a graph H , let for every edge . For and , let be a set of k‐edge‐connected K₃‐free graphs of order at most r and without spanning closed trails. We show that for given and ε, if H is a k‐connected claw‐free graph of order n with and , and if n is sufficiently large, then either H is Hamiltonian or the Ryjác?ek's closure where G is an essentially k‐edge‐connected K₃‐free graph that can be contracted to a graph in . As applications, we prove:

• (i) For , if and if and n is sufficiently large, then H is Hamiltonian.
• (ii) For , if and n is sufficiently large, then H is Hamiltonian.

These bounds are sharp. Furthermore, since the graphs in are fixed for given p and can be determined in a constant time, any improvement to (i) or (ii) by increasing the value of p and so enlarging the number of exceptions can be obtained computationally.     

A 2-factor with Short Cycles Passing Through Specified Independent Vertices in Graph

For a graph G, we define σ₂(G) := min{d(u) + d(v)|u, v ≠ ∈ E(G), u ≠ v}. Let k ≥ 1 be an integer and G be a graph of order n ≥ 3k. We prove if σ₂(G) ≥ n + k − 1, then for any set of k independent vertices v ₁,...,v _k , G has k vertex-disjoint cycles C ₁,..., C _k of length at most four such that v _i ∈ V(C _i ) for all 1 ≤ i ≤ k. And show if σ₂(G) ≥ n + k − 1, then for any set of k independent vertices v ₁,...,v _k , G has k vertex-disjoint cycles C ₁,..., C _k such that v _i ∈ V(C _i ) for all 1 ≤ i ≤ k, V(C ₁) ∪...∪ V(C _k ) = V(G), and |C _i | ≤ 4 for all 1 ≤ i ≤ k − 1. The condition of degree sum σ₂(G) ≥ n + k − 1 is sharp. Received: December 20, 2006. Final version received: December 12, 2007.     

The modified method of refined bounds for polyhedral approximation of convex polytopes

The modified method of refined bounds is proposed and experimentally studied. This method is designed to iteratively approximate convex multidimensional polytopes with a large number of vertices. Approximation is realized by a sequence of convex polytopes with a relatively small but gradually increasing number of vertices. The results of an experimental comparison between the modified and the original methods of refined bounds are presented. The latter was designed for the polyhedral approximation of multidimensional convex compact bodies of general type.     

关于q-树二次整子图和n阶加点q-树色多项式的注记

在这篇文章中我们成功地仅用色多项式表征了最小度不等于q-3的q-树的二次整子图和n阶加点q-树,即当图的最小度δ(G)≠q-3时,n阶图G具有色多项式P(G;λ)=λ(λ-1)…(λ-q+2)(λ-q+1)~3(λ-q)~(n-q-2), n≥q+2,当且仅当G是n阶q-树的二次整子图或n阶加点q-树.     

Central limit theorems for random polytopes

Let K be a smooth convex set. The convex hull of independent random points in K is a random polytope. Central limit theorems for the volume and the number of i dimensional faces of random polytopes are proved as the number of random points tends to infinity. One essential step is to determine the precise asymptotic order of the occurring variances. Research was supported in part by the European Network PHD, MCRN-511953.     

Actions of Picture Groups on CAT(0) Cubical Complexes

A class of groups, called picture groups, is defined. Richard Thompsons groups F, T, and V are all picture groups. Each picture group is shown to act properly and isometrically on a CAT(0) cubical complex. In particular, all picture groups are a-T-menable.Mathematics Subject Classifications (2000). 20F65, 43A15.     

On the Number of Vertices with Specified Eccentricity

The eccentricity of a vertex v in a graph is the maximum of the distances from v to all other vertices. The diameter of a graph is the maximum of the eccentricities of its vertices. Fix the parameters n, d, c. Over all graphs with order n and diameter d, we determine the maximum (within 1) and the minimum of the number of vertices with eccentricity c. Revised: May 7, 1999     

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

$\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     

预给二面角的m面凸多胞形嵌入Rd的充分必要条件

本文给出了预给二面角的ｍ面凸多胞形嵌入Ｒ^d的充分必要条件     

固定悬挂点的三圈图的无号拉普拉斯谱半径

In this paper,we determine the unique graph with the largest signless Laplacian spectral radius among all the tricyclic graphs with n vertices and k pendant vertices.     

The Willmore functional and the containment problem in R~4

Let∑be a convex hypersurface in the Euclidean space R4 with mean curvature H. We obtain a geometric lower bound for the Willmore functional∫∑H2dσ. This bound is an invariant involving the area of∑, the volume and Minkowski quermassintegrals of the convex body that∑bounds. We also obtain a sufficient condition for a convex body to contain another in the Euclidean space R4.     

包含子图K_4的无割点次极大图的唯一性

研究次极大图(即链环分支数等于基圈数的连通平图)的唯一性.证明了无割点且包含子图K_4的连通平图G是次极大图当且仅当G同构于K_4,并刻画了包含子图K_4的次极大图的结构.     

Martins' algorithm revisited for multi-objective shortest path problems with a MaxMin cost function

This paper presents a direct extension of the label setting algorithm proposed by Martins in 1984 for the shortest path problem with multiple objectives. This extended version computes all the efficient paths from a given source vertex, to all the other vertices of the network. The algorithm copes with problems in which the "cost values" associated with the network arcs are positive. The proposed extension can handle objective functions that are either of the "sum" type or of the "bottleneck" type. The main modifications to Martins' algorithm for multi-objective shortest path problems are linked to the dominance test and the procedure for identifying efficient paths. The algorithmic features are described and a didactic example is provided to illustrate the working principle. The results of numerical experiments concerning the number of efficient solutions produced and the CPU time consumed for several configurations of objectives, on a set of randomly generated networks, are also provided. Received: February 2005 / Revised version: June 2005 AMS classification: 90C29, 90C27, 05C38, 90B18, 68M12     

On the United Theory of the Family of Euler—Haller Type Methods with Cubical Convergence in Banach Spaces

The convergence problem of the family of Euler-Halley methods is considered under the Lipschitz condition with the L-average,and a united convergence theory with its applications is presented.     

A locally and cubically convergent algorithm for computing 𝒵‐eigenpairs of symmetric tensors

This paper is concerned with computing $\mathrm{??}$‐eigenpairs of symmetric tensors. We first show that computing $\mathrm{??}$‐eigenpairs of a symmetric tensor is equivalent to finding the nonzero solutions of a nonlinear system of equations, and then propose a modified normalized Newton method (MNNM) for it. Our proposed MNNM method is proved to be locally and cubically convergent under some suitable conditions, which greatly improves the Newton correction method and the orthogonal Newton correction method recently provided by Jaffe, Weiss and Nadler since these two methods only enjoy a quadratic rate of convergence. As an application, the unitary symmetric eigenpairs of a complex‐valued symmetric tensor arising from the computation of quantum entanglement in quantum physics are calculated by the MNNM method. Some numerical results are presented to illustrate the efficiency and effectiveness of our method.