共查询到20条相似文献,搜索用时 62 毫秒
1.
设DKv表示完全有向对称图,C(v,m)表示覆盖DKv的m长有向圈的最小圈数(称为覆盖数).对任意正整数m和v,当m≤v≤m+6时,覆盖数C(v,m) 被确定. 相似文献
2.
Let Kn be a complete graph on n vertices. In this paper, we find the necessary conditions for the existence of a 6-cycle system of Kn - L for every nearly 2-regular leave L of Kn. This condition is also sufficient when the number of vertices of L is n - 4. 相似文献
3.
4.
A tricyclic graph G =(V(G), E(G)) is a connected and simple graph such that|E(G)| = |V(G)|+2. Let Tg nbe the set of all tricyclic graphs on n vertices with girth g. In this paper, we will show that there exists the unique graph which has the largest signless Laplacian spectral radius among all tricyclic graphs with girth g containing exactly three(resp., four)cycles. And at the same time, we also give an upper bound of the signless Laplacian spectral radius and the extremal graph having the largest signless Laplacian spectral radius in Tg n,where g is even. 相似文献
5.
6.
给出了求解最大顶点覆盖问题的一种近似算法,讨论了它的性能保证,利用P ipage技术,为最大顶点覆盖问题设计出了0.75-近似算法. 相似文献
7.
A graph G is called quasi-claw-free if it satisfies the property:d(x,y)=2 there exists a vertex u∈N(x)∩N(y)such that N[u]■N[x]∪N[y].In this paper,we show that every 2-connected quasi-claw-free graph of order n with G■F contains a cycle of length at least min{3δ+2,n},where F is a family of graphs. 相似文献
8.
9.
农电营业区域的电费缴纳点选址研究是解决用电客户缴费难、购电难的关键课题之一,而当前大数据环境为电费缴纳点的合理布局提供了一个新的研究思路.首先通过运用基于数据点间"消息传递"的AP聚类算法从大量用电客户中筛选出候选电费缴纳选址点,然后采用集合覆盖模型对候选电费缴纳选址点进行再优化,得到最优选址点.并以赤峰市宁城县居民电力缴费记录与低压数据明细为例,为实现"村村都有缴费点"的建设目标,对较少用电客户的台区进行最优电费缴纳点选址研究.在此基础上,对最优电费缴纳点选址下的供电营业厅资源配置进行了分析,为供电公司在农电营业区域电费缴纳点的选址布局提供决策支持. 相似文献
10.
本文从最小连通顶点覆盖问题的求解算法出发,提出一种基于该问题本身的数学性质的降阶回溯算法来求解。通过基于问题的数学性质来设计精确算法,不仅能够克服使用启发式算法求解该问题在一般情形下都无法求得最优解的缺点,也改善了该问题使用传统精确算法时最坏时间复杂度高的缺点。本文首先研究该问题的数学性质,部分数学性质可成批确定某些顶点在或不在最小连通顶点覆盖集中,从而降低该问题的规模,提高精确算法的求解速度。其次,在数学性质的基础上,设计出上下界子算法、降阶子算法、回溯子算法来求解该问题的最优解。最后,时间复杂度分析以及无线网络设计的实例分析表明,该算法不仅能求得该问题的最优解,且相对一般精确算法,本文算法的时间复杂度更低。 相似文献
11.
For a graph G, we define σ2(G) := min{d(u) + d(v)|u, v ≠ ∈ E(G), u ≠ v}. Let k ≥ 1 be an integer and G be a graph of order n ≥ 3k. We prove if σ2(G) ≥ n + k − 1, then for any set of k independent vertices v
1,...,v
k
, G has k vertex-disjoint cycles C
1,..., C
k
of length at most four such that v
i
∈ V(C
i
) for all 1 ≤ i ≤ k. And show if σ2(G) ≥ n + k − 1, then for any set of k independent vertices v
1,...,v
k
, G has k vertex-disjoint cycles C
1,..., C
k
such that v
i
∈ V(C
i
) for all 1 ≤ i ≤ k, V(C
1) ∪...∪ V(C
k
) = V(G), and |C
i
| ≤ 4 for all 1 ≤ i ≤ k − 1.
The condition of degree sum σ2(G) ≥ n + k − 1 is sharp.
Received: December 20, 2006. Final version received: December 12, 2007. 相似文献
12.
Mekkia Kouider 《Combinatorica》2000,20(2):219-226
G =(V,E) is a 2-connected graph, and X is a set of vertices of G such that for every pair x,x' in X, , and the minimum degree of the induced graph <X> is at least 3, then X is covered by one cycle.
This result will be in fact generalised by considering tuples instead of pairs of vertices.
Let be the minimum degree in the induced graph <X>. For any ,
.
If , and , then X is covered by at most (p-1) cycles of G. If furthermore , (p-1) cycles are sufficient.
So we deduce the following:
Let p and t () be two integers.
Let G be a 2-connected graph of order n, of minimum degree at least t. If , and , then V is covered by at most cycles, where k is the connectivity of G.
If furthermore , (p-1) cycles are sufficient.
In particular, if and , then G is hamiltonian.
Received April 3, 1998 相似文献
13.
14.
图G包含4k个点,k≥2,如果σ_2(G)≥4k,则G包含k-2个4-圈和一个8-圈,并且这k-1个圈点不相交. 相似文献
15.
Zhi‐Hong Chen 《Journal of Graph Theory》2017,86(2):193-212
For a graph H , let for every edge . For and , let be a set of k‐edge‐connected K3‐free graphs of order at most r and without spanning closed trails. We show that for given and ε, if H is a k‐connected claw‐free graph of order n with and , and if n is sufficiently large, then either H is Hamiltonian or the Ryjác?ek's closure where G is an essentially k‐edge‐connected K3‐free graph that can be contracted to a graph in . As applications, we prove:
- (i) For , if and if and n is sufficiently large, then H is Hamiltonian.
- (ii) For , if and n is sufficiently large, then H is Hamiltonian.
16.
17.
Let G be a k(k ≤3)-edge connected simple graph with minimal degree ≥ 3,girth g,r=g12.For any independent set {a1,a2 , . . . , a 6/(4 k)} of G,if,then G is up-embeddable. 相似文献
18.
Thomassen proved that every ‐connected graph G contains an induced cycle C such that is k‐connected, establishing a conjecture of Lovász. In general, one could ask the following question: For any positive integers , does there exist a smallest positive integer such that for any ‐connected graph G, any with , and any , there is an induced cycle C in such that and is l‐connected? The case when is a well‐known conjecture of Lovász that is still open for . In this article, we prove and . We also consider a weaker version: For any positive integers , is there a smallest positive integer such that for every ‐connected graph G and any with , there is an induced cycle C in such that is l‐connected? The case when was studied by Thomassen. We prove and . 相似文献
19.
Yoshimi Egawa Ralph J. Faudree Ervin Györi Yoshiyasu Ishigami Richard H. Schelp Hong Wang 《Graphs and Combinatorics》2000,16(1):81-92
Dirac and Ore-type degree conditions are given for a graph to contain vertex disjoint cycles each of which contains a previously
specified edge. One set of conditions is given that imply vertex disjoint cycles of length at most 4, and another set of conditions
are given that imply the existence of cycles that span all of the vertices of the graph (i.e. a 2-factor). The conditions
are shown to be sharp and give positive answers to conjectures of Enomoto in [3] and Wang in [5].
Revised: July 28, 1999 相似文献
20.
关于哈密尔顿连通图的一个基本结果是Ore给出的:设G是n阶图,若对于任意两个不相邻顶点u和v,有d(u) d(v)≥n 1,则G是哈密尔顿连通的.设G是一个图,对于任意u (?)V(G),令N(U)=∪_(u∈∪)N(u),d(U)=|N(U)|,称d(U)是U的度.本文利用独立集的度和得到如下结果:设s和t是正整数,G是(2s 2t 1)-连通n阶图.若对于任两个强不交独立集S,T,|S|=s,|T|=t,有d(S) d(T)≥n 1.则G是哈密尔顿连通的.同时也得到图的哈密尔顿性的其它相关结果.两个独立集S和T称为强不交的,如果S∪T也是独立集. 相似文献