共查询到20条相似文献,搜索用时 15 毫秒
1.
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 相似文献
2.
以Banach空间的一般凸集为研究对象,将Banach空间的凸性研究推广到了内部非空的凸集上.打破了从单位球出发研究Banach空间几何的具有局限性的研究方法,给出了严格凸集的若干特征刻画及性质,并得到了严格凸集和光滑集之间的对偶定理. 相似文献
3.
Stefan Geschke Menachem Kojman 《Proceedings of the American Mathematical Society》2002,130(10):2871-2881
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 . 相似文献
4.
V. Yegnanarayanan 《Southeast Asian Bulletin of Mathematics》2000,24(1):129-136
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 相似文献
5.
6.
7.
8.
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!!! 相似文献
9.
设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。 相似文献
10.
James M. Carraher William B. Kinnersley Benjamin Reiniger Douglas B. West 《Journal of Graph Theory》2017,85(2):481-495
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 P4‐saturation game on . 相似文献
11.
郑宁国 《数学的实践与认识》2007,37(6):149-152
讨论了n个正数的Stolarsky平均的S-凸性和S-几何凸性,证明了:n元Stolarsky平均在r>1时是S-凸的和S-几何凸的;在r<1时是S-凹的.作为推论,此文也比较了n个正数的Stolarsky平均和算术平均的大小. 相似文献
12.
ANoteontheBondageNumberofaGraph¥LiYuqiang(DepartmentofMathematics,GuangzhouTeacher'sCollege)Abstract:Thebondagenumberb(G)ofag... 相似文献
13.
J. George Shanthikumar 《Queueing Systems》1994,16(3-4):287-299
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
1
,x
2
,x
3
,...) 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. 相似文献
14.
LI De-ming 《数学季刊》2005,20(2):121-127
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. 相似文献
15.
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. 相似文献
16.
设G是连通图,γ_C(G)和ir(G)分别表示G的连通控制数和无赘数。孙良于1990年证明了γ_c(G)≤4ir(G)—2,同时提出猜想γ_c(G)≤3ir(G)—2。本文进一步研究γ_c(G)与ir(G)的关系,并证得上述猜想成立。 相似文献
17.
局部凸空间的K强凸性与K强光滑性 总被引:3,自引:0,他引:3
首先引进了局部凸空间K强凸性的概念,它既是Banach空间K强凸性概念在局部凸空间中的推广,又是局部凸空间强凸性概念的自然推广;其次给出了局部凸空间K强凸性概念的对偶概念,即局部凸空间K强光滑性的概念,并得到了K强凸(K强光滑)的局部凸空间的特征刻画;最后,在P-自反的条件下给出了它们之间的对偶定理,即(X,TP)是K强凸(K强光滑)的当且仅当(X′,TP′)是K强光滑(K强凸)的. 相似文献
18.
谢力同 《数学物理学报(A辑)》2001,21(2):284-288
设犐是图犌的一个含有犽个点的独立集(简称犽独立集).如果犐不是犌的其它任何独立集的真子集,则称犐为犌的一个极大独立集.犌中所含的极大犽独立集的个数记为犿(犵犽,犌).设犵犽是图犌的任一个犽独立集,如果存在{狏1,狏2,…,狏犻}犞(犌)-犵犽,犻≥1,使得(1)对任意犼∈ {1,2,…,犻},犵犽+{狏犼}的都是犌的(犽+1) 独立集;(2)对任意狌∈犞(犌)-犵犽-{狏1,狏2,…,狏犻},犵犽+{狌}的都不是犌的独立集;则称犵犽为犌的一个犻爪犽独立集,犌所含的犻爪犽独立集的个数记为犿犻(犵犽,犌).该文证明了对简单图犌,犿犻(犵犽,犌)和犿(犵犽,犌)都是可重构的.另外,用同样的方法可以证明犌中的极大犽团的个数及犻爪犽团的个数也是可重构的. 相似文献
19.
给出了二元凸函数的定义,导出了二元凸函数的判别条件,该判别条件由二元函数的二阶导数给出.用二元凸函数的判别条件和半正定的(半负定)矩阵的性质,得到了二元二次多项式凸性的简单判别形式. 相似文献
20.
对广义Muirhead平均的Schur-幂凸性进行了讨论,给出了判定Muirhead平均的Schur-幂凸性的充要条件.结果改进了Chu和Xia在相关文献中的主要结果,Chu和Xia的结果是结果的特例. 相似文献