The 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 shortest path in G, while for a set S of vertices of G, the set I[S] is the union of all sets I[u,v] for u,v∈S. A set S is convex if I[S]=S. The convexity number con(G) of G is the maximum cardinality of a proper convex set of G. The clique number ω(G) is the maximum cardinality of a clique in G. If G is a connected graph of order n that is not complete, then n≥3 and 2≤ω(G)≤con(G)≤n−1. It is shown that for every triple l,k,n of integers with n≥3 and 2≤l≤k≤n−1, there exists a noncomplete connected graph G of order n with ω(G)=l and con(G)=k. Other results on convex numbers are also presented. Received: August 19, 1998 Final version received: May 17, 2000     

Banach空间上凸集的凸性

以Banach空间的一般凸集为研究对象,将Banach空间的凸性研究推广到了内部非空的凸集上．打破了从单位球出发研究Banach空间几何的具有局限性的研究方法,给出了严格凸集的若干特征刻画及性质,并得到了严格凸集和光滑集之间的对偶定理．     

Convexity numbers of closed sets in

For 2$"> let be the -ideal in generated by all sets which do not contain equidistant points in the usual metric on . For each 2$"> a set is constructed in so that the -ideal which is generated by the convex subsets of restricted to the convexity radical is isomorphic to . Thus is equal to the least number of convex subsets required to cover -- the convexity number of .

For every non-increasing function \aleph_0\}$"> we construct a model of set theory in which for each . When is strictly decreasing up to , uncountable cardinals are simultaneously realized as convexity numbers of closed subsets of . It is conjectured that , but never more than , different uncountable cardinals can occur simultaneously as convexity numbers of closed subsets of . This conjecture is true for and .     

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     

一类对称函数的Schur-几何凸性Schur-调和凸性

讨论一类对称函数的Schur-几何凸性和Schur-调和凸性.作为应用,利用控制理论,也得到一些新的分析不等式.     

一个模糊凸性的新的证明

用一种新的更传统的方法证明了在下半连续的条件下模糊凸性的两个充分条件.证明充分利用了下半连续即有最小值这一引理,没有沿用讨论该类模糊凸性问题常用方法,将模糊凸性的研究与传统分析中的有关内容融合、统一起来,给该类模糊凸性的研究提供了一种新的思路.     

积分凸性及其应用

该文在Banach空间中通过向量值函数的Bochner积分引进集合与泛函的积分凸性以及集合的积分端点等概念. 文章主要证明有限维凸集、开凸集和闭凸集均是积分凸集，下半连续凸泛函与开凸集上的上半连续凸泛函均是积分凸的, 非空紧集具有积分端点, 对紧凸集来说其积分端点集与端点集一致, 最后给出积分凸性在最优化理论方面的两个应用.     

Some Remarks on the Convexity Number of a Graph

Given a subgraph H in a graph G, we say H is convex if given any two vertices u and v in H, then H contains each shortest u–v path in G. As defined in [5], [8] and other places the convexity number of G, denoted con(G), is the order of a largest convex proper subgraph of G. We note that if G is not a complete graph, then the clique number of G forms a lower bound on con(G). As we shall see, in many graphs the clique number and convexity number are equal. We exploit this equality to show that computation of con is NP-complete, provide a Nordhaus-Gaddum type bound for con and produce a Ramsey type theorem for con. We shall see the latter two problems are closely related to classical Ramsey theory. In doing so, we answer a problem posed by Chartrand and Zhang in [5]. Acknowledgments.Respectfully dedicated to Professor Edgar M. Palmer, on the happy occasion of his retirement from Michigan State University. Professor Palmer's kind generosity to his students, colleagues and family is deeply appreciated by many. Salmon beware!!!     

一个图的匹配数条件

设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。     

The Game Saturation Number of a Graph

Given a family and a host graph H, a graph is ‐saturated relative to H if no subgraph of G lies in but adding any edge from to G creates such a subgraph. In the ‐saturation game on H, players Max and Min alternately add edges of H to G, avoiding subgraphs in , until G becomes ‐saturated relative to H. They aim to maximize or minimize the length of the game, respectively; denotes the length under optimal play (when Max starts). Let denote the family of odd cycles and the family of n‐vertex trees, and write F for when . Our results include , for , for , and for . We also determine ; with , it is n when n is even, m when n is odd and m is even, and when is odd. Finally, we prove the lower bound . The results are very similar when Min plays first, except for the P₄‐saturation game on .     

N元Stolarsky平均的凸性和几何凸性

讨论了n个正数的Stolarsky平均的S-凸性和S-几何凸性,证明了:n元Stolarsky平均在r>1时是S-凸的和S-几何凸的;在r<1时是S-凹的.作为推论,此文也比较了n个正数的Stolarsky平均和算术平均的大小.     

A Note on the Bondage Number of a Graph

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

Convexity of single stage queueing systems with bulk arrival

In this paper we study the convexity of the waiting time, workload and the number of jobs in single stage queueing systems with respect to the bulk size of the arrival process. In particular we show that the number of jobs in a single server queueing systemG ^[x ]/GI/1 and in a multiple server queueing systemG ^[x]/M/c with bulk sizesx=(x ₁ ,x ₂ ,x ₃ ,...) is componentwise convex inx. This is in the sense of the sample path convexity introduced in Shaked and Shanthikumar [11]. These results have applications in the stochastic comparison of bulk arrival queueing systems.Research supported in part by NSF grant DDM-9113008.     

图的分散数

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.     

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)的关系,并证得上述猜想成立。     

局部凸空间的K强凸性与K强光滑性

首先引进了局部凸空间K强凸性的概念,它既是Banach空间K强凸性概念在局部凸空间中的推广,又是局部凸空间强凸性概念的自然推广;其次给出了局部凸空间K强凸性概念的对偶概念,即局部凸空间K强光滑性的概念,并得到了K强凸(K强光滑)的局部凸空间的特征刻画;最后,在P-自反的条件下给出了它们之间的对偶定理,即(X,TP)是K强凸(K强光滑)的当且仅当(X′,TP′)是K强光滑(K强凸)的.     

论简单图所含k阶i爪独立集个数的可重构性

设犐是图犌的一个含有犽个点的独立集（简称犽独立集）．如果犐不是犌的其它任何独立集的真子集,则称犐为犌的一个极大独立集．犌中所含的极大犽独立集的个数记为犿（犵犽,犌）．设犵犽是图犌的任一个犽独立集,如果存在｛狏１,狏２,…,狏犻｝犞（犌）－犵犽,犻≥１,使得（１）对任意犼∈ ｛１,２,…,犻｝,犵犽＋｛狏犼｝的都是犌的（犽＋１） 独立集;（２）对任意狌∈犞（犌）－犵犽－｛狏１,狏２,…,狏犻｝,犵犽＋｛狌｝的都不是犌的独立集;则称犵犽为犌的一个犻爪犽独立集,犌所含的犻爪犽独立集的个数记为犿犻（犵犽,犌）．该文证明了对简单图犌,犿犻（犵犽,犌）和犿（犵犽,犌）都是可重构的．另外,用同样的方法可以证明犌中的极大犽团的个数及犻爪犽团的个数也是可重构的．     

二元凸函数的判别条件

给出了二元凸函数的定义,导出了二元凸函数的判别条件,该判别条件由二元函数的二阶导数给出.用二元凸函数的判别条件和半正定的(半负定)矩阵的性质,得到了二元二次多项式凸性的简单判别形式.     

关于广义Muirhead平均的Schur幂凸性

对广义Muirhead平均的Schur-幂凸性进行了讨论,给出了判定Muirhead平均的Schur-幂凸性的充要条件.结果改进了Chu和Xia在相关文献中的主要结果,Chu和Xia的结果是结果的特例.