Independence and hamiltonicity in 3-domination-critical graphs

Let δ, γ, i and α be respectively the minimum degree, the domination number, the independent domination number and the independence number of a graph G. The graph G is 3-γ-critical if γ = 3 and the addition of any edge decreases γ by 1. It was conjectured that any connected 3-γ-critical graph satisfies i = γ, and is hamiltonian if δ ≥ 2. We show here that every connected 3-γ-critical graph G with γ ≥ 2 satisfies α ≤ δ + 2; if α = δ + 2 then i = γ; while if α ≤ δ + 1 then G is hamiltonian. © 1997 Wiley & Sons, Inc. J Graph Theory 25: 173–184, 1997     

On P≥3-factor Deleted Graphs

A spanning subgraph F of a graph G is called a path factor of G if each component of F is a path.A P≥k-factor means a path factor with each component having at least k vertices, where k ≥ 2 is an integer.Bazgan, Benhamdine, Li and Wozniak [C. Bazgan, A. H. Benhamdine, H. Li, M. Wozniak, Partitioning vertices of 1-tough graph into paths, Theoret. Comput. Sci. 263(2001)255–261.] obtained a toughness condition for a graph to have a P_≥3-factor. We introduce the concept of a P_≥k...     

关于分数因子两个开问题的解答

本文指出极小连通二部分数1-因子不一定是极小2-连通图.研究了σ₂（G）与分数k-因子存在性之间的关系,指出存在一个特例在满足阶数n≥4k-5,δ（G）≥k且σ₂（G）≥n条件下,图G不存在分数k-因子.     

P3-支配图哈密尔顿性的两个充分条件

在文献[3]中介绍了一个新的图类-P3-支配图.这个图类包含所有的拟无爪图,因此也包含所有的无爪图.在本文中,我们证明了每一个点数至少是3的三角形连通的P3-支配图是哈密尔顿的,但有一个例外图K1,1,3.同时,我们也证明了k-连通的(k≥2)的P3-支配图是哈密尔顿的,如果an(G)≤k,但有两个例外图K1,1,3 and K2,3.     

Schrijver图SG(2k+2,k)的Hamilton性

通过图G的每个顶点的路称为Hamilton路,通过图G的每个顶点的圈称为Hamilton圈,具有Hamilton圈的图G称为Hamilton图.1952年Dirac曾得到关于Hamilton图一个充分条件的结论:图G有n个顶点,如果每个顶点υ满足:d(υ)≥n/2,则图G是Hamilton图.本文研究了Schrijver图SG(2k+2,k)的Hamilton性,采用寻找Hamilton圈的方法得出了Schrijver图SG(2k+2,k)是Hamilton图.     

On s‐Hamiltonian Line Graphs

For an integer s ≥ 0, a graph G is s‐hamiltonian if for any vertex subset with |S^′| ≤ s, G ‐ S^′ is hamiltonian. It is well known that if a graph G is s‐hamiltonian, then G must be (s+2)‐connected. The converse is not true, as there exist arbitrarily highly connected nonhamiltonian graphs. But for line graphs, we prove that when s ≥ 5, a line graph is s‐hamiltonian if and only if it is (s+2)‐connected.     

Degree conditions for k‐ordered hamiltonian graphs

For a positive integer k, a graph G is k-ordered hamiltonian if for every ordered sequence of k vertices there is a hamiltonian cycle that encounters the vertices of the sequence in the given order. It is shown that if G is a graph of order n with 3 ≤ k ≤ n/2, and deg(u) + deg(v) ≥ n + (3k − 9)/2 for every pair u, v of nonadjacent vertices of G, then G is k-ordered hamiltonian. Minimum degree conditions are also given for k-ordered hamiltonicity. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 199–210, 2003     

图有分数因子的度条件

本文研究了图有分数因子的度条件,得到了下面的结果：令k(?)1是一个整数,G是一个连通的n阶图,n(?)4k-3且最小度δ(G)(?)k,若对于每一对不相邻的顶点u,v∈V(G)都有max{d_G(u),d_G(v)}(?)n/2,则G有分数k-因子．并指出该结果在一定意义上是最好可能的。     

A generalization of a result of Bauer and Schmeichel

We prove that if G is a 1-tough graph withn ≥ 3 vertices such thatd(u) + d(v) +d(w) ≥n+ κ —2 holds for any triple of independent verticesu, v andw ofG, thenG is hamiltonian, wherek is the vertex connectivity ofG. This generalizes a recent result of Baur and Schmeichel.     

邻域并与泛圈图

本文中 ,我们用邻域并对泛圈图进行深入的研究 ,主要取得了“2连通 n( n≥ 3 )阶图 G,满足下列条件之一 ,则 G是泛圈图 : :δ≤ ( n-7) /3 ,N C≥ ( 2 n-3 ) /3 ; :( n-6) /3≤ δ≤ ( n+2 ) /3 ,N C≥ 2 n/3 ; :δ≥ ( n+3 ) /3 ,N C≥ ( 2 n-3 ) /3 .当 3≤ n≤ 14时 ,N C≥ 2 n/3”     

关于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是一个n阶3-连通图,周长为C(G),独立数为,若G是1-坚韧的,且,则G的每一个最长圈是控制圈且;又若G是5/3-坚韧的或,则G是Hamilton图。     

一个关于图是分数(k,n)-临界的邻域并条件

设G是一个图,以及k是满足1≤k的整数.一个图G在删除任意n个顶点后的子图均含有分数k-因子,则称G是一个分数(k,n)-临界图.给出了图是一个分数(k,n)-临界图的一个邻域并条件,并且该条件是最佳的.     

Independent dominating sets and hamiltonian cycles

A graph is uniquely hamiltonian if it contains exactly one hamiltonian cycle. In this note we prove that there are no r‐regular uniquely hamiltonian graphs when r > 22. This improves upon earlier results of Thomassen. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 233–244, 2007     

Bondy定理的改进

设G是一个n阶k连通图(k     

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

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

关于轮网络的一簇猜想

轮网络是由Cayley图模型设计出来的一种新型互连网络模型.星网络、冒泡排序网络、修正冒泡排序网络可嵌入轮网络.为了揭示它的整体结构,对轮网络提出如下一簇猜想:轮网络是边不交的i个Hamilton圈及2(n-i)-2个完美匹配的并,其中1≤i≤(n-1);并证明了当n=4,5,6,1≤i≤3时,猜想成立.     

New constructions of hypohamiltonian and hypotraceable graphs

A graph G is hypohamiltonian/hypotraceable if it is not hamiltonian/traceable, but all vertex‐deleted subgraphs of G are hamiltonian/traceable. All known hypotraceable graphs are constructed using hypohamiltonian graphs; here we present a construction that uses so‐called almost hypohamiltonian graphs (nonhamiltonian graphs, whose vertex‐deleted subgraphs are hamiltonian with exactly one exception, see [15]). This construction is an extension of a method of Thomassen [11]. As an application, we construct a planar hypotraceable graph of order 138, improving the best‐known bound of 154 [8]. We also prove a structural type theorem showing that hypotraceable graphs possessing some connectivity properties are all built using either Thomassen's or our method. We also prove that if G is a Grinbergian graph without a triangular region, then G is not maximal nonhamiltonian and using the proof method we construct a hypohamiltonian graph of order 36 with crossing number 1, improving the best‐known bound of 46 [14].     

Ore度和条件下赋权triangle-free图中的重圈(英文)

设G是一个2-连通赋权图,且G中每一对不相邻顶点u和v都满足d~w(u)+d~w(v)≥2d.Bondy等人证明了G或者包含一个哈密尔顿圈,或者包含一个权至少为2d的圈.如果G不是哈密尔顿图,这个结论意味着G中包含一个权至少为2d的圈.但是当G是哈密尔顿图时,我们不能判断G是否包含一个权至少为2d的圈.这篇文章中,在Fujisawa的一篇文章的启发下,我们证明了当G是triangle-free图并且|V(G)|是奇数时,G中一定包含一个权至少为2d的圈,即使G是哈密尔顿图.     

关于图是(r,n)-临界图的一个邻域条件

设n，m和r是满足r≥2，n≥0，m≥3的整数，且当r是奇数时，假设r≥m-1．称一个图为K1,m-free，如果它不包含以Kt,m为导出的子图．称一个图G为一个（r,n）-临界图，如果在删去G的任意n个点后，剩下G的子图都有一个r-因子,设G是一个Kl,m-free的（n＋1）-连通图，且阶为｜G｜以及r（｜G｜≥n）是偶数,证明了：如果G的最小度至少是r＋n＋m-1，阶｜G｜≥8r5＋n，并且对V（G）的任意独立点集{x1，x2}都有｜NG（x1）∪NG（x2）｜≥（｜G｜＋n）／2，那么G是一个（r,n）-临界图．关于G的最小度和｜NG（x1）∪NG（X2）｜的下界是紧的。