共查询到17条相似文献,搜索用时 211 毫秒
1.
设e是3连通图G的一边。如果G-e是某个3连通图的剖分,则称e是G的可去边。用v表示G的顶点数,本文证明了当v≥6时,3连通平面图G的可去边数的下界是v+4/2,此下界是可以达到的。 相似文献
2.
G是3-连通图,e是G中的一条边.若G-e是3-连通图的一个剖分,则称e是3-连通图的可去边.否则,e是G中不可去边.本给出3-连通3-正则图中生成树外可去边的分布情况及数目. 相似文献
3.
4.
连通图G的边修正Szeged指标Sze*(G)定义为■,其中mu(e|G),mv(e|G),m0(e|G)分别是G中到u点比到v点距离近的边的数目、到v点比到u点距离近的边的数目、以及到u,v两点距离同样近的边的数目.本文通过变换和计算得到了给定直径的单圈图的边修正Szeged指标的下界,并刻画了达到下界的极值图. 相似文献
5.
正则图的限制性边连通度 总被引:1,自引:0,他引:1
将连通图分离成阶至少为二的分支之并的边割称为限制性边割,最小限制性边割的阶称为限制性边连通度.
用λ′(G)表示限制性连通度,则λ′(G)≤ξ(G),其中ξ(G)表示最小边度.
如果上式等号成立,则称G是极大限制性边连通的. 本文证明了当k>|G|/2时,k正则图G是极大限制性边连通的,其中k≥2,
|G|≥4; k的下界在某种程度上是不可改进的. 相似文献
6.
7.
4连通图的可去边与4连通图的构造 总被引:2,自引:0,他引:2
本文引进了4连通图的可去边的概念,,并证明了4连通图G中不存在可去边的充要条件是G=C5或C6,同时给出了n阶4连通图的一个新的构造方法. 相似文献
8.
9.
欧见平 《数学物理学报(A辑)》2005,25(6):863-868
3限制边割是连通图的一个边割, 它将此图分离成阶不小于3的连通分支. 图G的最小3限制边割所含的边数称为此图的3限制边连通度, 记作λ\-3(G). 它以图G的3阶连通点导出 子图的余边界的最小基数ξ_3(G)为上界. 如果λ_3(G)=ξ_3(G), 则称图G是极大3限制边连通的 . 已知在某种程度上,3限制边连通度较大的网络有较好的可靠性. 作者在文中证明: 如果k正则连通点可迁图的 围长至少是5, 那么它是是极大3限制边连通的. 相似文献
10.
设P(G,λ)表示图G的色多项式.给定正整数n,e和λ,记f(v,e,λ)=max{P(G,λ):G是个v点e边的图}.本文得到f(v,e,λ)的新上界和f(v,e,3)的新下界. 相似文献
11.
Mader and Jackson independently proved that every 2‐connected simple graph G with minimum degree at least four has a removable cycle, that is, a cycle C such that G/E(C) is 2‐connected. This paper considers the problem of determining when every edge of a 2‐connected graph G, simple or not, can be guaranteed to lie in some removable cycle. The main result establishes that if every deletion of two edges from G remains 2‐connected, then, not only is every edge in a removable cycle but, for every two edges, there are edge‐disjoint removable cycles such that each contains one of the distinguished edges. © 2002 Wiley Periodicals, Inc. J Graph Theory 42: 155–164, 2003 相似文献
12.
An edge e of a k-connected graph G is said to be a removable edge if G O e is still k-connected, where G e denotes the graph obtained from G by deleting e to get G - e, and for any end vertex of e with degree k - 1 in G- e, say x, delete x, and then add edges between any pair of non-adjacent vertices in NG-e (x). The existence of removable edges of k-connected graphs and some properties of 3-connected and 4-connected graphs have been investigated [1, 11, 14, 15]. In the present paper, we investigate some properties of 5-connected graphs and study the distribution of removable edges on a cycle and a spanning tree in a 5- connected graph. Based on the properties, we proved that for a 5-connected graph G of order at least 10, if the edge-vertex-atom of G contains at least three vertices, then G has at least (3│G│ + 2)/2 removable edges. 相似文献
13.
An edge of a 5‐connected graph is said to be 5‐removable (resp. 5‐contractible) if the removal (resp. the contraction) of the edge results in a 5‐connected graph. A 5‐connected graph with neither 5‐removable edges nor 5‐contractible edges is said to be minimally contraction‐critically 5‐connected. We show the average degree of every minimally contraction‐critically 5‐connected graph is less than . This bound is sharp in the sense that for any positive real number ε, there is a minimally contraction‐critically 5‐connected graph whose average degree is greater than . 相似文献
14.
充分利用图的字典积的结构证明了以下结论:如果图G_1的每连通分支都非平凡,图G_2的阶数大于3,那么它们的字典积G_1[G_2]具有非零3-流. 相似文献
15.
设图G是一个K-正则连通点可迁图.如果G不是极大限制性边连通的,那么G含有一个(k-1)-因子,它的所有分支都同构于同一个阶价于k和2k-3之间的点可迁图.此结果在某种程度上加强了Watkins的相应命题:如果k正则点可迁图G不是k连通的,那么G有一个因子,它的每一个分支都同构于同一个点可迁图. 相似文献
16.
设G是一个阶不小于6的k正则连通点可迁图. 如果G不含三角形, 那么图G是极大3限制边连通的, 或者G含有各连通分支都同构于同一个h阶点可迁图的k-1正则因子, 其中2k-2≤h≤3k-5. 唯一的例外是: G是围长等于4 的3正则图. 相似文献
17.
围长为3的点可迁图的3限制边连通度 总被引:1,自引:0,他引:1
设G是阶至少为6的k正则连通图.如果G的围长等于3,那么它的3限制边连通度 λ3(G)≤3k-6.当G是3或者4正则连通点可迁图时等号成立,除非G是4正则图并且 λ3(G)=4.进一步,λ3(G)=4的充分必要条件是图G含有子图K4. 相似文献