一类无奇洞图的色数

给定图G,我们称G中长度至少为4的导出圈为G的洞,长度为奇数或偶数的洞分别被称为是奇洞或偶洞.我们用HVN来表示一个由K₄添加一个点并向K₄连两条边所得的图,用H表示长为7的圈的补图.Chudnovsky等人在[J.Combin.Theory B,2010,100:313-331]中证明了每一个无奇洞且无K₄的图是4-可染的,且其色数为4当且仅当其含有H为导出子图.在本文中,我们将这一结论推广到无奇洞且无HVN的图类上.设G是一个无奇洞且无HVN的图,我们证明了若G含有H为导出子图,则G有一个特殊的割集或者属于两类特殊图,作为推论我们证明了X（G）≤ω（G）+1,且等号成立当且仅当ω（G）=3且G含有H为导出子图,从而完全确定了这类图的色数.     

图的距离无符号拉普拉斯谱半径的关于色数的下界

Let G be a connected graph on n vertices with chromatic number k, and let ρ(G)be the distance signless Laplacian spectral radius of G. We show that ρ(G) ≥ 2n + 2「n k」- 4,with equality if and only if G is a regular Tur′an graph.     

Mycielski图的循环色数

通过引入一类点集划分的概念,研究了Mylielski图循环染色的性质,证明了当完全图的点数足够大时,它的Mycielski图的循环色数与其点色数相等.     

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

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

星形图乘积的pebbling数

图 G的 pebbling数 f(G)是最小的整数 n,使得不论 n个 pebble如何放置在 G的顶点上 ,总可以通过一系列的 pebbling移动把一个 pebble移到任意一个顶点上 ,其中的 pebbling移动是从一个顶点上移走两个 pebble而把其中的一个移到与其相邻的一个顶点上 .设 K1,n为 n+1个顶点的星形图 .本文证明了 (n+2 )(m+2 )≥ f K1,n× K1,m)≥ (n+1) (m+1) +7,n>1,m>1.     

一类运算图的匹配数

设G是一个简单图,把G的每条边e=(a,b)变换成一个三角形ae^*b而得到一个新图,记为R (G), 其中新增加的顶点e^*的度为2.本文证明R (G)的匹配数完全由图G的顶点度序列确定.     

一个图的匹配数条件

设G是一个简单图,在图G中任意一个最大匹配的基数叫做G的匹配数,记作v(G),在这篇文章中我们获得了下面的结果,(1)设G是连通的和不完全的,则对于x,y∈v(G)和xyE(G),v(G-{x,y}=v(G)-1的充分必要条件是(a)G[A(G)]是完全的和A(G)的每一个点和C(G)的每一个点相邻,(b)c(D(G))=|A(G)| 1,和(c)y∈D(G-x)对于x,y∈C(G)。(2)设G是连通的和不完全的,则v(G-{x,y})=v(G)-2对于x,y∈V(G)和xyE(G)的充分必要条件是GK_(n,n),其中n≥2。     

用Paley图计算对角Ramsey数下界的新方法

本文研究了对角Paley数的下界问题.利用一个新发现的Paley图的自同构,给出了计算Paley图团数的一个新方法,获得了2个对角Rasey数的新下界:R(20,20)≥18877,R(21,21)≥25949.     

色数等于选择数的4-正则图

设Hn(n≥5)表示一个图:以1,2,．．．,n为顶点,两个点i和j是相邻的当且仅当|i-j|≤2,其中加法取模n．这篇文章证明了,Hn的色数等于它的选择数．结果被用于刻画最大度至多2的图的列表全色数．     

图的分散数

The decay number of a connected graph is defined to be the minimum number of the components of the cotree of the graph. Upper bounds of the decay numbers of graphs are obtained according to their edge connectivities. All the bounds in this paper are tight. Moreover, for each integer k between one and the upper bound, there are infinitely many graphs with the decay number k.     

A lower bound on the acyclic matching number of subcubic graphs

The acyclic matching number of a graph $G$ is the largest size of an acyclic matching in $G$, that is, a matching $M$ in $G$ such that the subgraph of $G$ induced by the vertices incident to edges in $M$ is a forest. We show that the acyclic matching number of a connected subcubic graph $G$ with $m$ edges is at least $m∕6$ except for two graphs of order 5 and 6.     

A lower bound for the interval number of a graph

The interval number i(G) of a graph G with n vertices is the lowest integer m such that G is the intersection graph of some family of sets I₁,…,I_n with every I_i being the union of at most m real intervals. In this article a lower bound for i(G) is proved followed by some considerations about the construction of graphs that are critical with respect to the interval number.     

A lower bound for the convexity number of some graphs

Given a connected graphG, we say that a setC ?V(G) is convex inG if, for every pair of verticesx, y ∈ C, the vertex set of everyx-y geodesic inG is contained inC. The convexity number ofG is the cardinality of a maximal proper convex set inG. In this paper, we show that every pairk, n of integers with 2 ≤k ≤ n?1 is realizable as the convexity number and order, respectively, of some connected triangle-free graph, and give a lower bound for the convexity number ofk-regular graphs of ordern withn>k+1.     

A new lower bound on the number of trivially noncontractible edges in contraction critical 5-connected graphs

An edge of a k-connected graph is said to be k-contractible if its contraction results in a k-connected graph. A k-connected non-complete graph with no k-contractible edge, is called contraction critical k-connected. An edge of a k-connected graph is called trivially noncontractible if its two end vertices have a common neighbor of degree k. Ando [K. Ando, Trivially noncontractible edges in a contraction critically 5-connected graph, Discrete Math. 293 (2005) 61-72] proved that a contraction critical 5-connected graph on n vertices has at least n/2 trivially noncontractible edges. Li [Xiangjun Li, Some results about the contractible edge and the domination number of graphs, Guilin, Guangxi Normal University, 2006 (in Chinese)] improved the lower bound to n+1. In this paper, the bound is improved to the statement that any contraction critical 5-connected graph on n vertices has at least trivially noncontractible edges.     

A note on the signed edge domination number in graphs

Let G=(V(G),E(G)) be a graph. A function f:E(G)→{+1,−1} is called the signed edge domination function (SEDF) of G if ∑_e^′N[e]f(e^′)≥1 for every eE(G). The signed edge domination number of G is defined as is a SEDF of G}. Xu [Baogen Xu, Two classes of edge domination in graphs, Discrete Applied Mathematics 154 (2006) 1541–1546] researched on the edge domination in graphs and proved that for any graph G of order n(n≥4). In the article, he conjectured that: For any 2-connected graph G of order n(n≥2), . In this note, we present some counterexamples to the above conjecture and prove that there exists a family of k-connected graphs G_m,k with .     

On edge domination numbers of graphs

Let and be the signed edge domination number and signed star domination number of G, respectively. We prove that holds for all graphs G without isolated vertices, where n=|V(G)|?4 and m=|E(G)|, and pose some problems and conjectures.     

The lower bound on independence number

Let G be a graph with degree sequence ( d_v). If the maximum degree of any subgraph induced by a neighborhood of G is at most m, then the independence number of G is at least , where f_m+1( x) is a function greater than for x> 0. For a weighted graph G = ( V, E, w), we prove that its weighted independence number (the maximum sum of the weights of an independent set in G) is at least where w_v is the weight of v.     

图的局部减边控制数

引入局部减边控制函数和局部减边控制数的概念,得到了图的最小局部减边控制函数的性质,给出了局部减边控制数的最好上下界,确定了一些特殊图的局部减边控制数.最后得到了图的减边控制数的最好上界.