Minimal D-splitting and SD-splitting for a Compression Body

In this paper, we fix the genus of SD-splittings of a compression body. We also discuss the uniqueness for minimal D-splittings and SD-splittings for a han-dlebody.     

Weakly Disk-busting Curves in the Boundary of a Compression Body

Let V be a nontrivial compression body which is not simple.An essential simple closed curve J in (З)+ V is called weakly disk-busting if (З)+ V-J has only one compressing disk up to isotopy.In this paper,we give an upper bound of the diameter of the image of boundaries of essential disks in V under any projection determined by a weakly disk-busting curve.Moreover,we give a sufficient condition for the handle additions to be boundary irreducible.     

两个压缩体融合为一个压缩体的充分必要条件北大核心CSCD

本文给出了两个压缩体沿紧致连通曲面(带边曲面或闭曲面)融合仍是一个压缩体(有非空负边界)的充分必要条件,还给出了两个3维流形沿着边界上的紧致连通带边曲面融合中的融合曲面为边界不可压缩的一个特征描述,同时还证明了压缩体的每个Heegaard分解是标准的.     

Spanning trees in a cactus

We prove a best possible lower bound for the number of isomorphism classes into which all rooted spanning trees of a rooted cactus partition. We announce a best possible lower bound for the number of isomorphism classes into which all spanning trees of a cactus partition.     

Spanning caterpillars of a hypercube

Spanning trees of the hypercube Q_n have been recently studied by several authors. In this paper, we construct spanning trees of Q_n which are caterpillars and establish quantitative bounds for a caterpillar to span Q_n. As a corollary, we disprove a conjecture of Harary and Lewinter on the length of the spine of a caterpillar spanning Qⁿ. © 1997 John Wiley & Sons, Inc.     

On a Spanning K-tree Containing Specified Vertices in a Graph

Acta Mathematicae Applicatae Sinica, English Series - A k-tree is a tree with maximum degree at most k. In this paper, we give a sharp degree sum condition for a graph to have a spanning k-tree in...     

Spanning trails

For a graph G with distinguished vertices u and v, we give a sufficient condition for the existence of a (u, v)-trail containing every vertex of G.     

Spanning multi-paths in hypercubes

A set A of vertices of a hypercube is called balanced if . We prove that for every natural number n there exists a natural number π₁(n) such that for every hypercube Q with dim(Q)?π₁(n) there exists a family of pairwise vertex-disjoint paths P_i between A_i and B_i for i=1,2,…,n with if and only if {A_i,B_i∣i=1,2,…,n} is a balanced set.     

Spanning triangulations in graphs

We prove that every graph of sufficiently large order n and minimum degree at least 2n/3 contains a triangulation as a spanning subgraph. This is best possible: for all integers n, there are graphs of order n and minimum degree ?2n/3? ? 1 without a spanning triangulation. © 2005 Wiley Periodicals, Inc. J Graph Theory     

On a Spanning Tree with Specified Leaves

Let k ≥ 2 be an integer. We show that if G is a (k + 1)-connected graph and each pair of nonadjacent vertices in G has degree sum at least |G| + 1, then for each subset S of V(G) with |S| = k, G has a spanning tree such that S is the set of endvertices. This result generalizes Ore’s theorem which guarantees the existence of a Hamilton path connecting any two vertices. Dedicated to Professor Hikoe Enomoto on his 60th birthday.     

Spanning trees and a conjecture of Kontsevich

Kontsevich conjectured that the number of zeros over the fieldF _q of a certain polynomialQ _G associated with the spanning trees of a graphG is a polynomial function ofq. We show the connection between this conjecture, the Matrix-Tree Theorem, and orthogonal geometry. We verify the conjecture in certain cases, such as the complete graph, and discuss some modifications and extensions.Partially supported by NSF grant #DMS-9743966.     

Spanning Annuli in 3—manifolds

Al3-manifOldsandsurfacesconsideredinthisPaperareassumedtobecompactandori-entable,andallconcePtsandnotationsnotdefinedinthepaperareStandardfsee,forexample[2,3j.AcompressionbodyHisconstructedbyadding2-handlestoSXIalongacollectionofpairwisdisjointsimpleclosedcurvesonSX{o},andcaPpingoffanyresulting2-spherebound-arycomponentSwith3-balls,whereSisaconnectedclosedorientablesurface.ThecomponentSX{1}Of8Hisdenoted8 Handthesurface8H-8 H,whichmayormaynotbeconnect-ed,isdenoted8H.If8H=gi,Hisahandleb…     

Change Intolerance in Spanning Forests

Call a percolation process on edges of a graph change intolerant if the status of each edge is almost surely determined by the status of the other edges. We give necessary and sufficient conditions for change intolerance of the wired spanning forest when the underlying graph is a spherically symmetric tree.     

Spanning trees in hyperbolic graphs

We construct spanning trees in locally finite hyperbolic graphs that represent their hyperbolic compactification in a good way: so that the tree has at least one but at most a bounded number of disjoint rays to each boundary point. As a corollary we extend a result of Gromov which says that from every hyperbolic graph with bounded degrees one can construct a tree (disjoint from the graph) with a continuous surjection from the ends of the tree onto the hyperbolic boundary such that the surjection is finite-to-one. We shall construct a tree with these properties as a subgraph of the hyperbolic graph, which in addition is also a spanning tree of that graph.     

Rooted Spanning Trees in Tournaments

A tournament of order n is an orientation of a complete graph with n vertices, and is specified by its vertex set V(T) and edge set E(T). A rooted tree is a directed tree such that every vertex except the root has in-degree 1, while the root has in-degree 0. A rooted k-tree is a rooted tree such that every vertex except the root has out-degree at most k; the out-degree of the root can be larger than k. It is well-known that every tournament contains a rooted spanning tree of depth at most 2; and the root of such a tree is also called a king in the literature. This result was strengthened to the following one: Every tournament contains a rooted spanning 2-tree of depth at most 2. We prove that every tournament of order n≥800 contains a spanning rooted special 2-tree in this paper, where a rooted special 2-tree is a rooted 2-tree of depth 2 such that all except possibly one, non-root, non-leaf vertices, have out-degree 2 in the tree. Revised: November 9, 1998     

Spanning network games

We study fundamental properties of monotone network enterprises which contain public vertices and have positive and negative costs on edges and vertices. Among the properties studied are the nonemptiness of the core, characterization of nonredundant core constraints, ease of computation of the core and the nucleolus, and cases of decomposition of the core and the nucleolus. Received December 1994/Final version March 1998     

Spanning Trees with a Bounded Number of Branch Vertices in a Claw-Free Graph

Let k be a non-negative integer. A branch vertex of a tree is a vertex of degree at least three. We show two sufficient conditions for a connected claw-free graph to have a spanning tree with a bounded number of branch vertices: (i) A connected claw-free graph has a spanning tree with at most k branch vertices if its independence number is at most 2k + 2. (ii) A connected claw-free graph of order n has a spanning tree with at most one branch vertex if the degree sum of any five independent vertices is at least n ? 2. These conditions are best possible. A related conjecture also is proposed.