A local structure theorem on 5‐connected graphs

An edge of a 5‐connected graph is said to be contractible if the contraction of the edge results in a 5‐connected graph. Let x be a vertex of a 5‐connected graph. We prove that if there are no contractible edges whose distance from x is two or less, then either there are two triangles with x in common each of which has a distinct degree five vertex other than x, or there is a specified structure called a K₄^?‐configuration with center x. As a corollary, we show that if a 5‐connected graph on n vertices has no contractible edges, then it has 2n/5 vertices of degree 5. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 99–129, 2009     

Invariant algebraic curves of large degree for quadratic system

In this paper we present for the first time examples of algebraic limit cycles and saddle loops of degree greater than 4 for planar quadratic systems. In particular, we give examples of algebraic limit cycles of degree 5 and 6, and algebraic saddle loops of degree 3 and 5 surrounding a strong focus. We also give an example of an invariant algebraic curve of degree 12 for which the quadratic system has no Darboux integrating factors or first integrals.     

Describing 4-paths in 3-polytopes with minimum degree 5

Back in 1922, Franklin proved that each 3-polytope with minimum degree 5 has a 5-vertex adjacent to two vertices of degree at most 6, which is tight. This result has been extended and refined in several directions. In particular, Jendrol’ and Madaras (1996) ensured a 4-path with the degree-sum at most 23. The purpose of this note is to prove that each 3-polytope with minimum degree 5 has a (6, 5, 6, 6)-path or (5, 5, 5, 7)-path, which is tight and refines both above mentioned results.     

Rational curves of degree 16 on a general heptic fourfold

According to a conjecture of H. Clemens, the dimension of the space of rational curves on a general projective hypersurface should equal the number predicted by a naïve dimension count. In the case of a general hypersurface of degree 7 in P⁵${\mathbb{P}}^5$, the conjecture predicts that the only rational curves should be lines. This has been verified by Hana and Johnsen for rational curves of degree at most 15. Here we extend their results to show that no rational curves of degree 16 lie on a general heptic fourfold.     

List total colorings of planar graphs without triangles at small distance

Suppose that G is a planar graph with maximum degree Δ. In this paper it is proved that G is total-(Δ + 2)-choosable if (1) Δ ≥ 7 and G has no adjacent triangles (i.e., no two triangles are incident with a common edge); or (2) Δ ≥ 6 and G has no intersecting triangles (i.e., no two triangles are incident with a common vertex); or (3) Δ ≥ 5, G has no adjacent triangles and G has no k-cycles for some integer k ∈ {5, 6}.     

收缩临界5-连通图的平均度

M．Kriesell证明了收缩临界5-连通图的平均度不超过24并猜想收缩临界5-连通图的平均度小于10．本文构造了一个反例证明M．Kriesell的猜想不成立并给出了收缩临界5-连通图平均度新的上界．     

标准序列逻辑系统S_3中公式的概率真度理论

利用势为3的非均匀概率空间的无穷乘积在三值标准序列逻辑系统中引入了公式的概率真度概念,证明了全体公式的概率真度值之集在[0,1]中没有孤立点;利用概率真度定义了概率相似度和伪距离,进而建立了概率逻辑度量空间,证明了该空间中没有孤立点,为三值命题的近似推理理论提供了一种可能的框架.     

Total domination of graphs and small transversals of hypergraphs

The main result of this paper is that every 4-uniform hypergraph on n vertices and m edges has a transversal with no more than (5n + 4m)/21 vertices. In the particular case n = m, the transversal has at most 3n/7 vertices, and this bound is sharp in the complement of the Fano plane. Chvátal and McDiarmid [5] proved that every 3-uniform hypergraph with n vertices and edges has a transversal of size n/2. Two direct corollaries of these results are that every graph with minimal degree at least 3 has total domination number at most n/2 and every graph with minimal degree at least 4 has total domination number at most 3n/7. These two bounds are sharp.     

The height of a 4-cycle in triangle-free 1-planar graphs with minimum degree 5

A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by at most one other edge. It is known that each 1-planar graph has a vertex of degree at most 7, and also either a vertex of degree at most 4 or a cycle of length at most 4. In the article, it is proven that each triangle-free 1-planar graph of degree less than 5 has a 4-cycle that consists of vertices of degree at most 8.     

三值逻辑系统W3中的随机化研究

利用赋值集的随机化方法,在三值逻辑W3中提出了公式的随机真度,证明了所有公式的随机真度之集在[0,1]中没有孤立点;给出了两公式间的DW3-相似度与伪距离的概念,并建立了DW3-逻辑度量空间,证明了此空间没有孤立点.     

On well-covered triangulations: Part III

A graph G is said to be well-covered if every maximal independent set of vertices has the same cardinality. A planar (simple) graph in which each face is a triangle is called a triangulation. It was proved in an earlier paper Finbow et al. (2004) [3] that there are no 5-connected planar well-covered triangulations, and in Finbow et al. (submitted for publication) [4] that there are exactly four 4-connected well-covered triangulations containing two adjacent vertices of degree 4. It is the aim of the present paper to complete the characterization of 4-connected well-covered triangulations by showing that each such graph contains two adjacent vertices of degree 4.     

Non-isochronicity of the center at the origin in polynomial Hamiltonian systems with even degree nonlinearities

In 2002 X. Jarque and J. Villadelprat proved that no center in a planar polynomial Hamiltonian system of degree 4 is isochronous and raised a question: Is there a planar polynomial Hamiltonian system of even degree which has an isochronous center? In this paper we give a criterion for non-isochronicity of the center at the origin of planar polynomial Hamiltonian systems. Moreover, the orders of weak centers are determined. Our results answer a weak version of the question, proving that there is no planar polynomial Hamiltonian system with only even degree nonlinearities having an isochronous center at the origin.     

Quasi-minimal enumeration degrees and minimal Turing degrees

We show that there exists a set A such that A has quasi-minimal enumeration degree, and there are uncountably many sets B such that A is enumeration reducible to B and B has minimal Turing degree. Answering a related question raised by Solon, we also show that there exists a nontotal enumeration degree which is not e-hyperimmune.During the preparation of this paper, Slaman was partially supported by the HCM European Program no. ERBCHRXCT930415 (while he was visiting the University of Leeds), by NSF Grant DMS-9500878 and was a CNR Visiting Professor at the University of Siena.The preparation of this paper was partially supported by the HCM European Program no. ERBCHRXCT930415 and by MURST 60%.     

On a conjecture of Lempp

In this paper, we first prove that there exist computably enumerable (c.e.) degrees a and b such that , and for any c.e. degree u, if and u is cappable, then , so refuting a conjecture of Lempp (in Slaman [1996]); secondly, we prove that: (A. Li and D. Wang) there is no uniform construction to build nonzero cappable degree below a nonzero c.e. degree, that is, there is no computable function such that for all (i) , (ii) has a cappable degree, and (iii) unless Received: 19 Otober 1998     

The chromatic number of oriented graphs

We introduce in this paper the notion of the chromatic number of an oriented graph G (that is of an antisymmetric directed graph) defined as the minimum order of an oriented graph H such that G admits a homomorphism to H. We study the chromatic number of oriented k-trees and of oriented graphs with bounded degree. We show that there exist oriented k-trees with chromatic number at least 2^k+1 - 1 and that every oriented k-tree has chromatic number at most (k + 1) × 2^k. For 2-trees and 3-trees we decrease these upper bounds respectively to 7 and 16 and show that these new bounds are tight. As a particular case, we obtain that oriented outerplanar graphs have chromatic number at most 7 and that this bound is tight too. We then show that every oriented graph with maximum degree k has chromatic number at most (2k - 1) × 2^2k-2. For oriented graphs with maximum degree 2 we decrease this bound to 5 and show that this new bound is tight. For oriented graphs with maximum degree 3 we decrease this bound to 16 and conjecture that there exists no such connected graph with chromatic number greater than 7. © 1997 John Wiley & Sons, Inc. J Graph Theory 25: 191–205, 1997     

Vertices of Degree 5 in a Contraction Critically 5-connected Graph

An edge of a k-connected graph is said to be k-contractible if the contraction of the edge results in a k-connected graph. A k-connected graph with no k-contractible edge is said to be contraction critically k-connected. We prove that a contraction critically 5-connected graph on n vertices has at least n/5 vertices of degree 5. We also show that, for a graph G and an integer k greater than 4, there exists a contraction critically k-connected graph which has G as its induced subgraph.     

SOME RESULTS ON BUDS,STEMS AND FAULT TOLERANCE IN HYPERCUBES OF DIMENSION ⋚ 5

Abstract

We determine the minimum number of faulty links in a 5-dimensional hypercube so that no 2-dimensional subcube is fault free. The degree sequences of some related extremal graphs are also determined.     

Invariant cubature formulas for the hyperoctahedron

Cubature formulas for calculating integrals over the hyperoctahedron that are invariant under the group of all of its orthogonal transformations are obtained. Two of them are exact for all polynomials of degree no greater than seven and one is exact for all polynomials of degree no greater than five. Translated fromMatematicheskie Zametki, Vol. 61, No. 5, pp. 734–741, May, 1997. Translated by V. N. Dubrovsky     

Decomposition of cubic graphs related to Wegner’s conjecture

Thomassen formulated the following conjecture: Every 3-connected cubic graph has a red–blue vertex coloring such that the blue subgraph has maximum degree 1 (that is, it consists of a matching and some isolated vertices) and the red subgraph has minimum degree at least 1 and contains no 3-edge path. We prove the conjecture for Generalized Petersen graphs.We indicate that a coloring with the same properties might exist for any subcubic graph. We confirm this statement for all subcubic trees.