极小拟(k+1)连通图的最小度

给出了极小拟5连通图有围长大于或等于4的极小拟（k）＋1连通图的最小度。     

关于k-消去二分图的一些结果

图 G的一个 k-正则支撑子图称为 G的 k-因子 ,若对 G的任一边 e,图 G- e总存在一个 k-因子 ,则称 G是 k-消去图 .证明了二分图 G=( X,Y) ,且 | X | =| Y|是 k-消去图的充分必要条件是 k| S|≤ r1 + 2 r2 +…+ k( rk+… + rΔ) - ε( S)对所有 S X成立 .并由此给出二分图是 k-消去图的充分度条件 .     

3—连通局部连通无爪图是泛连通图

本文证明了若G是连通、局部连通的无爪图,则G是泛连通图的充要条件为G是3-连通图.这意味着H.J.Broersma和H.J.Veldman猜想成立.     

k-边连通图的新充分谱条件

令G是一个简单连通图.如果连通图G被删除少于k条边后仍然保持连通,则称G是k-边连通的.基于图G或补图■的距离谱半径,距离无符号拉普拉斯谱半径,Wiener指数和Harary指数,提供了图G是k-边连通的新充分谱条件,从而建立了图的代数性质与结构性质之间的紧密联系.     

关于联图P_1VP_n的k-强优美性

本文研究了联图P_1VP_n的k-强优美性问题.利用K-强优美图的定义,获得了联图P_1VP_n是k-强优美图的必要条件,还得到了当n:2k-1时联图P_1VP_n是k-强优美图,亦是k-优美图,及当n≥3时联图P_1VP_n是2-强优美图,也是2-优美图的结果,推广了联图P_1VP_n是优美图的结果.     

Hamilton连通图的一个充分条件

Let G be a3-connected graph with n vertices.The paper proves that if for each pair of verti-ces u and v of G,d(u,v)=2,has|N(u)∩N(v)|≤α（αis the minimum independent set num-ber),and then max{d(u),d(v)|≥n 1/2,then G is a Hamilton connected graph.     

关于一类边裂图的k-边幻性

通常没有有效的方法判别一般图G的k-边幻性.本文采用分析方法,讨论了一类非均匀边裂图SPE(Cn,h)的边幻性和k-边幻性,得到一些新的结果.     

n阶本原极小强连通有向图k-指数的最小值

本文证明了:当1≤k≤︱n/4︱时,n阶本原极小强连通有向图k指数的最小值是4。     

2-连通无爪图的连通因子

若图G不含有同构于K1,3的导出子图,则称G为一个无爪图.令a和b是两个整数满足2≤a≤b.本文证明了若G是一个含有[a,b]因子的2连通无爪图,则G有一个连通的[a,b 1]因子.     

A result on quasi k-connected graphs

Let G be a k-connected graph, and T be a subset of V(G)If G- T is not connected,then T is said to be a cut-set of GA k-cut-set T of G is a cut-set of G with |T | = kLet T be a k-cut-set of a k-connected graph GIf G- T can be partitioned into subgraphs G1 and G2 such that |G1| ≥ 2, |G2| ≥ 2, then we call T a nontrivial k-cut-set of GSuppose that G is a(k- 1)-connected graph without nontrivial(k- 1)-cut-setThen we call G a quasi k-connected graphIn this paper, we prove that for any integer k ≥ 5, if G is a k-connected graph without K-4, then every vertex of G is incident with an edge whose contraction yields a quasi k-connected graph, and so there are at least|V(G)|2edges of G such that the contraction of every member of them results in a quasi k-connected graph.     

Note on 2-edge-colorings of complete graphs with small monochromatic k-connected subgraphs

Bollob′as and Gy′arf′as conjectured that for n4(k-1) every 2-edge-coloring of Kn contains a monochromatic k-connected subgraph with at least n-2k+2 verticesLiu, et alproved that the conjecture holds when n≥13k-15In this note, we characterize all the2-edge-colorings of Kn where each monochromatic k-connected subgraph has at most n-2k+2 vertices for n≥13k-15.     

Removable edges in a spanning tree of a k-connected graph

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 O e denotes the graph obtained from G by the following way： deleting e to get G - e, and for any end vertex of e with degree k - 1 in G - e, say x, deleting x, and then adding 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 k-connected graphs have been investigated. In the present paper, we investigate the distribution of removable edges on a spanning tree of a k-connected graph （k ≥ 4）.     

A note on degree-continuous graphs

The minimum orders of degree-continuous graphs with prescribed degree sets were investigated by Gimbel and Zhang, Czechoslovak Math. J. 51 (126) (2001), 163–171. The minimum orders were not completely determined in some cases. In this note, the exact values of the minimum orders for these cases are obtained by giving improved upper bounds.     

A note on vertex-transitive non-Cayley graphs from Cayley graphs generated by involutions

We show that the result of Watkins (1990) [19] on constructing vertex-transitive non-Cayley graphs from line graphs yields a simple method that produces infinite families of vertex-transitive non-Cayley graphs from Cayley graphs generated by involutions. We also prove that the graphs arising this way are hamiltonian provided that their valency is at least six.     

A note on minimal matching covered graphs

A graph is called matching covered if for its every edge there is a maximum matching containing it. It is shown that minimal matching covered graphs without isolated vertices contain a perfect matching.     

A note on vertex pancyclic oriented graphs

Let D be an oriented graph of order n ≥ 9, minimum degree at least n − 2, such that, for the choice of distinct vertices x and y, either xy ∈ E(D) or d⁺(x) + d⁻(y) ≥ n − 3. Song (J. Graph Theory 18 (1994), 461–468) proved that D is pancyclic. In this note, we give a short proof, based on Song's result, that D is, in fact, vertex pancyclic. This also generalizes a result of Jackson (J. Graph Theory 5 (1981), 147–157) for the existence of a hamiltonian cycle in oriented graphs. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 313–318, 1999     

A note on minimum degree conditions for supereulerian graphs

A graph is called supereulerian if it has a spanning closed trail. Let G be a 2-edge-connected graph of order n such that each minimal edge cut SE(G) with |S|3 satisfies the property that each component of G−S has order at least (n−2)/5. We prove that either G is supereulerian or G belongs to one of two classes of exceptional graphs. Our results slightly improve earlier results of Catlin and Li. Furthermore, our main result implies the following strengthening of a theorem of Lai within the class of graphs with minimum degree δ4: If G is a 2-edge-connected graph of order n with δ(G)4 such that for every edge xyE(G) , we have max{d(x),d(y)}(n−2)/5−1, then either G is supereulerian or G belongs to one of two classes of exceptional graphs. We show that the condition δ(G)4 cannot be relaxed.     

A note on the domination dot-critical graphs

A graph G is dot-critical if contracting any edge decreases the domination number. Nader Jafari Rad (2009) [3] posed the problem: Is it true that a connected k-dot-critical graph G with G^′=0? is 2-connected? In this note, we give a family of 1-connected 2k-dot-critical graph with G^′=0? and show that this problem has a negative answer.