共查询到20条相似文献,搜索用时 250 毫秒
1.
设G是连通图,γ_C(G)和ir(G)分别表示G的连通控制数和无赘数。孙良于1990年证明了γ_c(G)≤4ir(G)—2,同时提出猜想γ_c(G)≤3ir(G)—2。本文进一步研究γ_c(G)与ir(G)的关系,并证得上述猜想成立。 相似文献
2.
设G是连通图。用r_c(G)、r_c(G)和ir(G)分别表示G的连通Domination数、全Domination数和Irredundance数,本文证明了下列结论: (1) r_c(G)≤3ir(G)-2 (2)r_c(G)≤2r_t(G)-2 相似文献
3.
王春香 《数学物理学报(A辑)》2009,29(1):145-150
如果图G的一个集合X中任两个点不相邻, 则称 X 为独立集合. 如果 N[X]=V(G), 则称X是一个控制集合. i(G)(β(G))分别表示所有极大独立集合的最小(最大)基数. γ(G)(Γ(G))表示所有极小控制集合的最小(最大)基数. 在这篇论文中, 作者证明如下结论: (1) 如果 G ∈R 且G 是n阶3 -正则图, 则 γ(G)= i(G), β(G)=n/3. (2) 每个n阶连通无爪3 -正则图 G, 如果 G(G≠ K4) 且不含诱导子图K4-e, 则 β(G) =n/3. 相似文献
4.
设G是一个图。G的最小度,连通度,控制数,独立控制数和独立数分别用δ,k,γ,i和α表示,图G是3-γ-临界的,如果γ=3,而且G增加任一条边所得的图的控制数为2.Sumner和Blitch猜想:任意连通的3-γ临界图满足i=3,本文证明了如果G是使α=k 1≤δ的连通3-γ-临界图,那么Sumner-Blitch猜想成立。 相似文献
5.
6.
3-γ-临界图G中关于i(G)=γ(G)的一个充分条件 总被引:1,自引:0,他引:1
如果图G满足γ(G)=k且对图G中任两个相邻的点x,y有γ(G+xy)=k-1,则称图G为k-γ-临界图,如果图G满足γ(G)=k且对图G中任何距离为d的两点x,y有γ(G+xy)=k-1,则称图G为k-(γ,d)-临界图。Sumner和Blitch猜想在3-γ-临界图中有γ(G)=i(G).Oellermann和Swart猜想3-(γ,2)-临界图中有γ(G)=i(G),这篇文章中我们提出3-γ-临界图中使γ(G)=i(G)的一个充分条件。 相似文献
7.
我们分别用γ(G),β(G)和α(G)表示图G的控制数、匹配数和覆盖数,对任意连通图,有γ(G)≤β(G)≤α(G)成立,1998年,Randerath和Volkmann给出了控制数等于覆盖数的图的特征,本文首先证明了匹配数与控制数相等的图其最小度不超过2,而后给出了最小度为2的图的结构性质。 相似文献
8.
图G的圈点连通度,记为κ_c(G),是所有圈点割中最小的数目,其中每个圈点割S满足G-S不连通且至少它的两个分支含圈.这篇文章中给出了两个连通图的笛卡尔乘积的圈点连通度:(1)如果G_1≌K_m且G_2≌K_n,则κ_c(G_1×G_2)=min{3m+n-6,m+3n-6},其中m+n≥8,m≥n+2,或n≥m+2,且κ_c(G_1×G_2)=2m+2n-8,其中m+n≥8,m=n,或n=m+1,或m=n+11;(2)如果G_1≌K_m(m≥3)且G_2■K_n,则min{3m+κ(G_2)-4,m+3κ(G_2)-3,2m+2κ(G_2)-4}≤κ_c(G_1×G_2)≤mκ(G2);(3)如果G_1■K_m,K_(1,m-1)且G_2■K_n,K_(1,n-1),其中m≥4,n≥4,则min{3κ(G_1)+κ(G_2)-1,κ(G_1)+3κ(G_2)-1,2_κ(G_1)+2_κ(G_2)-2}≤κ_c(G_1×G_2)≤min{mκ(G_2),nκ(G_1),2m+2n-8}. 相似文献
9.
《数学的实践与认识》2013,(15)
引入了图的符号星k限定控制的概念,从而求出了星图和轮图的符号星k控制数.还刻画了满足γ′_(ss)(G)=1/2(2r+s)的图,基中γ′_(ss)(G)表示图G的符号星控制数.最后对图的符号星部分控制的已有结果作了改进. 相似文献
10.
设tγ(G)为G的全控制数.证明了:(1)对广义θ-图G,tγ(G)≤α(G) 1;(2)对任意k-正则无爪图G,k≥3,有tγ(G)≤α(G).这里α(G)表示G的匹配数.作为结果(2)的推论,对k-正则无爪图(k≥3),证明了Favaron猜想是成立的.即对最小度不小于3的简单图,有tγ(G)≤12 V(G).此外,举例说明了当图的最小度不超过2时,对一般图而言,匹配数与全控制数不可比较. 相似文献
11.
本文研究了一类整数序列(2n)2n 1的某些性质,利用费玛数和数论函数的某些性质,获得了验证此类整数是否是亲和数和完全数的方法,既不与其他正整数构成亲和数对也不是完全数. 相似文献
12.
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 相似文献
13.
Kyriakos Keremedis 《Mathematical Logic Quarterly》1999,45(1):95-104
We find topological characterizations of the pseudointersection number ?? and the tower number t of the real line and we show that ?? < t iff there exists a compact separable T2 space X of π-weight < ?? that can be covered by < t nowhere dense sets iff there exists a weak Hausdorff gap of size K < t, i. e., a pair ({A : i ≠ k}, {BJ : j ε K}) C [W]W X [U]W such that A = {Ai : i ε K} is a decreasing tower, B = {Bj : j ε K) is a family of pseudointersections of A, and there is no pseudointersection S of A meeting each member of B in an infinite set. 相似文献
14.
Bohdan Zelinka 《Czechoslovak Mathematical Journal》2005,55(2):393-396
The restrained domination number r(G) and the total restrained domination number
t
r
(G) of a graph G were introduced recently by various authors as certain variants of the domination number (G) of (G). A well-known numerical invariant of a graph is the domatic number d(G) which is in a certain way related (and may be called dual) to (G). The paper tries to define analogous concepts also for the restrained domination and the total restrained domination and discusses the sense of such new definitions.This research was supported by Grant MSM 245100303 of the Ministry of Education, Youth and Sports of the Czech Republic. 相似文献
15.
Futaba Okamoto Ping Zhang Varaporn Saenpholphat 《Czechoslovak Mathematical Journal》2008,58(1):271-287
For a nontrivial connected graph G of order n and a linear ordering s: v
1, v
2, …, v
n
of vertices of G, define . The traceable number t(G) of a graph G is t(G) = min{d(s)} and the upper traceable number t
+(G) of G is t
+(G) = max{d(s)}, where the minimum and maximum are taken over all linear orderings s of vertices of G. We study upper traceable numbers of several classes of graphs and the relationship between the traceable number and upper
traceable number of a graph. All connected graphs G for which t
+(G) − t(G) = 1 are characterized and a formula for the upper traceable number of a tree is established.
Research supported by Srinakharinwirot University, the Thailand Research Fund and the Commission on Higher Education, Thailand
under the grant number MRG 5080075. 相似文献
16.
Jing-wen Li Zhi-wen Wang Jaeun Lee Moo Young Sohn Zhong-fu Zhang En-qiang Zhu 《应用数学学报(英文版)》2010,26(3):525-528
In this paper we get some relations between α(G), α'(G), β(G), β'(G) and αT(G), βT(G). And all bounds in these relations are best possible, where α(G), α'(G),/3(G), β(G), αT(G) and βT(G) are the covering number, edge-covering number, independent number, edge-independent number (or matching number), total covering number and total independent number, respectively. 相似文献
17.
设n是大于1的正常数,并且设n=pα11p2α2…ptαt,其中pi为素数,i=1,2,…,t,ω(n)表示n的不同素因子的个数,即ω(n)=t.若n的所有因子的倒数和为整数,即0≤∑ij≤αjj=1,2,…,t1p1i1pi22…ptit为整数,称n是调和数.证明了和调和数相关的一个结论. 相似文献
18.
Let k≥2 be an integer,and let σ(n) denote the sum of the positive divisors of an integer n.We call n a quasi-multiperfect number if σ(n)=kn+1.In this paper,we give some necessary properties of them. 相似文献
19.
20.
Izolda Gorgol 《Graphs and Combinatorics》2008,24(4):327-331
A subgraph of an edge-colored graph is called rainbow if all of its edges have different colors. For a graph H and a positive integer n, the anti-Ramsey number f (n, H) is the maximum number of colors in an edge-coloring of K
n
with no rainbow copy of H. The rainbow number
rb(n, H) is the minimum number of colors such that any edge-coloring of K
n
with rb(n, H) number of colors contains a rainbow copy of H. Certainly rb(n, H) = f(n, H) + 1. Anti-Ramsey numbers were introduced by Erdős et al. [4] and studied in numerous papers.
We show that for n ≥ k + 1, where C
k
+ denotes a cycle C
k
with a pendant edge. 相似文献