图的结合数猜想的新结果

［１］中Ｗｏｏｄａｌ猜想：若图Ｇ的结合数ｂｉｎｄ（Ｇ）≥３２,则图Ｇ包含三角形,本文证明：若ｂｉｎｄ（Ｇ）≥７＋√６９１０,则图Ｇ包含三角形,从而进一步改进了［２］的结果     

图的结合数猜想的新结果

[1]中Woodall猜想：若图G的结合数bind(G)≥3/2．则图G包含三角形．本证明：若bind(G)≥7-√69/10,则图G包含三角形．从而进一步改进了[2]的结果。     

关于风车图中一个猜想的证明

证明了 [2 ]中猜想 :风车图 Kt3是强协调图的充分必要条件是 t≡ 0 ,1 ( mod4)     

关于Mycielski图循环色数的猜想

通过引进Mycielski图点集的一类特殊划分,利用该划分在Mycielski图循环着色中的特点改进了如下猜想:完全图的Mycielski图的循环色数等于它的点色数.     

关于超Euler图的一个猜想的注记

本文研究了Catlin的关于超Euler图的一个猜想,借助于收缩方法,得到了该猜想的两个充分条件.     

关于拟阵基图一个猜想的证明

设G是一个拟阵的基图,κ(G),λ(G)和δ(G)分别是G的连通度、边连通度和最小次数,文献[1]给出了下面的猜想:κ(G)=λ(G)-δ(G),本文将证明上述猜想是正确的。     

费马数是复合数的一个充要条件

费马数是复合数的一个充要条件梅义元（武汉市张家湾中学４３００６５）众所周知，形如的数叫做费马敖．当Ｆｎ是素数时，高斯曾证明了正Ｆｎ边形可以仅用圆规与直尺来作图．因此研究费马数是非常有意义的．我们已经知道，若Ｆｎ有质因子Ｐ，则Ｐ的形状为Ｐ＝２ｎ＋１ｋ＋...     

图的2-控制数的上界和一个Graffiti.pc猜想（英文）

设G=(V(G),E(G))是一个图,k是一个正整数.称一个顶点子集S为G的kk-控制集,若V(G)\S中的每个顶点在S中至少有k个邻点,我们用r_k (G)表示kk-控制集的最小阶数.令d₁≤d₂≤…≤d_n为图G的度序列.当n为偶数时,度序列中位数m(G)=d_n/2+1,当n为奇数时,度序列中位数m(G)=d_n+1/2.一个仍未解决的Graffiti.pc猜想说:对任一n个顶点的连通图G,r₂(G)≤n-m(G)+1.首先我们证明了此猜想的一个弱形式:r2(G) ≤n-d₁+1.此外,通过拓展此猜想在二部图上的结果,我们证明了对最小度不小于2的无三角形图G,r2(G)≤n-Δ(G),其中Δ(G)为图G的最大度.众所周知,每一个其边数不少于顶点数的图都包含一个圈.我们将此结论推广到超图上.进而得到上述猜想对所有分裂图都成立.     

算术图一个猜想的证明

Ａｃｈａｒｙａ和Ｈｅｄｇｅ提出猜想：(i)若圈Ｃ_4t＋１( t≥1, t∈N) 是(k, d )－算术图，则Ｋ＝２ｄｔ+ 2r ( r≥0, r∈N ) ; ( ii) 若圈C_4t＋3是(k, d )-算术图, 则k= (2t+ 1) d + 2r ( r≥0, r∈N ). 本文证明了上述猜想为真.     

关于图的点可区别边染色的一个猜想

图G的一个k-正常边染色f被称为点可区别的是指任意两个不同点的点及其关联边所染色集合不同,所用最少染色数被称为G的点可区别边色数,张忠辅教授提出一猜想即对每一个正整数k≥3,总存在一个最大度为△(G)=k≥3的图G,,满足图G一定有一个子图H,且母图的点可区别的边色数小于子图的.本文证明了对于最大度小于9时,此猜想正确.     

Disproof of a Conjecture on the Subdivision Domination Number of a Graph

A set S of vertices of a graph G = (V,E) is a dominating set if every vertex of is adjacent to some vertex in S. The domination number γ(G) is the minimum cardinality of a dominating set of G. The domination subdivision number sd_γ(G) is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the domination number. Haynes et al. (Discussiones Mathematicae Graph Theory 21 (2001) 239-253) conjectured that for any graph G with . In this note we first give a counterexample to this conjecture in general and then we prove it for a particular class of graphs.     

图的连通控制数与无赘数的一个不等式

设G是连通图,γ_C(G)和ir(G)分别表示G的连通控制数和无赘数。孙良于1990年证明了γ_c(G)≤4ir(G)—2,同时提出猜想γ_c(G)≤3ir(G)—2。本文进一步研究γ_c(G)与ir(G)的关系,并证得上述猜想成立。     

A Note on the Bondage Number of a Graph

ＡＮｏｔｅｏｎｔｈｅＢｏｎｄａｇｅＮｕｍｂｅｒｏｆａＧｒａｐｈ￥ＬｉＹｕｑｉａｎｇ（ＤｅｐａｒｔｍｅｎｔｏｆＭａｔｈｅｍａｔｉｃｓ，ＧｕａｎｇｚｈｏｕＴｅａｃｈｅｒ＇ｓＣｏｌｌｅｇｅ）Ａｂｓｔｒａｃｔ：Ｔｈｅｂｏｎｄａｇｅｎｕｍｂｅｒｂ（Ｇ）ｏｆａｇ...     

The Pseudoachromatic Number of a Graph

The pseudoachromatic number of a graph G is the maximum size of a vertex partition of G (where the sets of the partition may or may not be independent) such that, between any two distinct parts, there is at least one edge of G. This parameter is determined for graphs such as cycles, paths, wheels, certain complete multipartite graphs, and for other classes of graphs. Some open problems are raised.AMS Subject Classification (1991): primary 05C75 secondary 05C85     

Graph pegging numbers

In graph pegging, we view each vertex of a graph as a hole into which a peg can be placed, with checker-like “pegging moves” allowed. Motivated by well-studied questions in graph pebbling, we introduce two pegging quantities. The pegging number (respectively, the optimal pegging number) of a graph is the minimum number of pegs such that for every (respectively, some) distribution of that many pegs on the graph, any vertex can be reached by a sequence of pegging moves. We prove several basic properties of pegging and analyze the pegging number and optimal pegging number of several classes of graphs, including paths, cycles, products with complete graphs, hypercubes, and graphs of small diameter.     

A Sharp Upper Bound for the Number of Spanning Trees of a Graph

Let G = (V,E) be a simple graph with n vertices, e edges and d₁ be the highest degree. Further let λ_i, i = 1,2,...,n be the non-increasing eigenvalues of the Laplacian matrix of the graph G. In this paper, we obtain the following result: For connected graph G, λ₂ = λ₃ = ... =  λ_n-1 if and only if G is a complete graph or a star graph or a (d₁,d₁) complete bipartite graph. Also we establish the following upper bound for the number of spanning trees of G on n, e and d₁ only:

The Forcing Convexity Number of a Graph

For two vertices u and v of a connected graph G, the set I(u,v) consists of all those vertices lying on a u-v geodesic in G. For a set S of vertices of G, the union of all sets I(u,v) for u, v S is denoted by I(S). A set S is a convex set if I(S) = S. The convexity number con(G) of G is the maximum cardinality of a proper convex set of G. A convex set S in G with |S| = con(G) is called a maximum convex set. A subset T of a maximum convex set S of a connected graph G is called a forcing subset for S if S is the unique maximum convex set containing T. The forcing convexity number f(S, con) of S is the minimum cardinality among the forcing subsets for S, and the forcing convexity number f(G, con) of G is the minimum forcing convexity number among all maximum convex sets of G. The forcing convexity numbers of several classes of graphs are presented, including complete bipartite graphs, trees, and cycles. For every graph G, f(G, con) con(G). It is shown that every pair a, b of integers with 0 a b and b is realizable as the forcing convexity number and convexity number, respectively, of some connected graph. The forcing convexity number of the Cartesian product of H × K ₂ for a nontrivial connected graph H is studied.