边赋权图支撑树权的介值性

有关图的介值性,已有若干较好的结果,但这些结果都未涉及图的赋权。本文考虑边赋权图支撑树权的介值性。证明了定理A 设双射w:E(G)→{1,2,…|E(G)|}是连通图G=(V(G),E(G))的边赋权,如果存在G的圈基使w在它的每个圈上的象集为连续整数集,则w((G))={w(e)|T∈J(G)}是连续整数集。其中(G)是G的支撑树的集合。     

一个在置换图中寻找DFS树的最优算法

本是通过在连通置换图中构造辅助树的方法,给出了一个在具有n个顶点的置换图G中寻找深度优先支撑树（简称,DFS树）的最优算法,并证明了该算法的时间复杂性为O(n)。     

关于k—消去图的若干新结果

设G是一个图．k是自然数．图G的一个k-正则支撑子图称为G的一个k-因子．若对于G的每条边e．G—e都存在一个k-因子，则称G是一个k-消去图．该文得到了一个图是k-消去图的若干充分条件，推广了文［2—4］中有关结论．     

关于图值随机元的若干概率不等式

设{Xi}∞i=1是一列独立同分布在图Γ=(V(Γ),E(Γ))上取值的随机元.本文给出在图上取值随机元的r-阶均值集与r-阶广义样本均值集的概念,将经典的Chebyshev及Hoeffding型不等式推广到图值随机元序列中.     

图的光滑支架分解

设G是一个图,A为其边集的子集。G的一个支架分解是（G－A,A）,其中G－A是去掉A后的连通图,G的一个光滑支架分解是适合下列条件的支架分解：（1）G－A的每一叶具有连通余树;（2）G－B（G－A）割边集为A,其中B（G－A）为G－A的割边集。本文给出了求一个图的光辉支架分解的一个有效算法。     

最短时限运输问题及图上求解法

提出了最短时限运输问题,借助于赋权二分图研究了其解的最优性充要条件,并给出了在赋权二分图上求解的具体步骤,最后给出了一个实例。事实证明,该法是一个有效的算法     

有向图中几类支撑树数目的计算公式

将W.T.Tultte提出的计算有向图中以某点为根的支撑出树数目的公式推广到了更一般的情况,并给出了有向图中具有不同特点的支撑树数目的计算公式。     

图的介值定理的变异形式

本文对目前已知的图的一系列介值定理给出几种变异形式。     

几类图的支撑树的个数

推广了计算图的支撑树个数的递归公式,解释了组合计数原理的用法.用组合技巧和常系数线性递归序列的解法,对n步梯、n-棱柱、Mobius n-棱柱及有关图,找到了计算它们的支撑树的个数的若干公式.     

关于集值优化问题的若干结果

引入了集值集值C-τ-半预不变凸概念，证明了集值集值C-τ-半预不变凸优化问题的局部弱有效元是弱有效元，给出了集值预不变凸变分不等式作为集值C-τ-半预不变凸优化问题的充分条件和必要条件，这些结果推广了文[1-4]的相应结果。     

Graphs with only caterpillars as spanning trees

A connected graph G is caterpillar-pure if each spanning tree of G is a caterpillar. The caterpillar-pure graphs are fully characterized. Loosely speaking they are strings or necklaces of so-called pearls, except for a number of small exceptional cases. An upper bound for the number of edges in terms of the order is given for caterpillar-pure graphs, and those which attain the upper bound are characterized.     

图的介值定理的变异形式(英)

本文对目前已知的图的一系列介值定理给出了几种变异形式．     

关于k—覆盖图的一些新结果

本文给出了一个图G是k-覆盖图的若干充分条件．     

没有5-圈的平面图的BB-染色

设H为G的一个生成子图,（G,H）的一个BB-k-染色是指一个映射f：V（G）→{1,2,…,k},当uv∈E（H）,｜f（u）-f（v）｜≥2;当uv∈E（G）／E（H）,｜f（u）-f（v）｜≥1.定义（G,H）的BB色数x_b（G,H）为最小的整数k,使得（G,H）是BB-k可染的.本文研究了对于任意的连通,非二部平面图G,且G没有5-圈,都存在一棵生成树T,使得x_b（G,T）=4.     

一些图的生成树数

图 G 的生成树是它的连通子图(子树).本文精确地计算出了一些图的生成树的数目, 例如双心轮图、双柄扇图等等.     

Graphs, networks, and linear unbiased estimates

It is shown how a best linear unbiased estimate (blue) in the additive variety-block setting can be interpreted as a network flow, that is, a function on edges that obeys the Kirkhhoff laws, of minimum square norm. An explicit expression is then obtained for the coefficients of the blue in terms of invariants of the underlying network; specifically, the invariants are: the total number of spanning trees and the number of certain selective yet specific spanning forests with just two trees. The blue is also expressed as a linear combination of bases of paths in a constructive manner. It remains a conjecture as to whether there always exists a basis of paths in which the blue is a convex combination. Consequences to design optimality are explored.     

Connected Factors and Spanning Trees in Graphs

 Let G be a graph, and g, f, f′ be positive integer-valued functions defined on V(G). If an f′-factor of G is a spanning tree, we say that it is f′-tree. In this paper, it is shown that G contains a connected (g, f+f′−1)-factor if G has a (g, f)-factor and an f′-tree. Received: October 30, 2000 Final version received: August 20, 2002     

树图的1—Hamilton连通性

一阶数≥3的简单连通图叫做1-Hamilton连通的,若对每一对顶点v_1、v_2及任一边v_2v_3(v_1≠v_3),存在连接v_1和v_2,并且经过v_3v_2的Hamilton路.本文中我们证明:连通图的树图或是1-Hamilton连通的,或为一超立方体,或同构于K_2×K_3和W_5之一.     

Some results on spanning trees

Some structures of spanning trees with many or less leaves in a connected graph are determined.We show（1） a connected graph G has a spanning tree T with minimum leaves such that T contains a longest path,and（2） a connected graph G on n vertices contains a spanning tree T with the maximum leaves such that Δ（G） =Δ（T） and the number of leaves of T is not greater than n D（G）＋1,where D（G） is the diameter of G.     

Some Existence Theorems on Path Factors with Given Properties in Graphs

A path factor of G is a spanning subgraph of G such that its each component is a path.A path factor is called a P≥_n-factor if its each component admits at least n vertices. A graph G is called P≥_n-factor covered if G admits a P≥_n-factor containing e for any e ∈ E(G), which is defined by[Discrete Mathematics, 309, 2067–2076(2009)]. We first define the concept of a(P≥_n, k)-factor-critical covered graph, namely, a graph G is called(P≥_n, k)-factor-critical covered if G-D is P≥_n-factor covered for any D ? V(G) with |D| = k. In this paper, we verify that(i) a graph G with κ(G) ≥ k + 1 is(P≥2, k)-factor-critical covered if bind(G) 2+k/3;(ii) a graph G with |V(G)| ≥ k + 3 and κ(G) ≥ k + 1 is(P≥3, k)-factor-critical covered if bind(G) ≥4+k/3.