共查询到20条相似文献,搜索用时 13 毫秒
1.
p阶临界2-边连通图的最大边数 总被引:2,自引:0,他引:2
设G=(V,E)是2-边连通图,若对每个点v∈V,G-v不是2-边连通图,则称G是临界2-边连通图. 本文证明了p阶临界2-边连通图的最大边数是 7, P=6; (1/8)(P~2+4p) p=0(mod 4); f(p)= (1/8)(P~2+2p+13) p=1(mod 4); (1/8)(P~2+28) p=(2mod 4),p≠6 (1/8)(P~2+2p+9) p=3(mod 4)。并且给出了达到最大边数的极值图. 相似文献
2.
本文中未经说明的术语和记号采自[2].设 G=(V,E)是一个简单图。G 的顶点数记作 n(G),边数记作 m(G),即 n(G)=|V|,m(G)=|E|.假设 G 是3-边连通图.G 的顶点 v(?)V 称为 G 的临界点,如果 G-v 不是3-边连通的;否则称为 G 的非临界点.如果每个 v(?)V 都是 G 临界点,则称 G 是临界3-边连通图.临界3-边连通图类记作 A,A_n 是 A 中所有 n 阶图的集合.假设 G(?)A,则对每个 v∈A, 相似文献
3.
图G称为k-临界h-边-连通的,若h=λ(G)且对每个k顶点集{u1,…,uk}有λ(G-{u1,…,ui})≤λ(G-{u1,…,ui-1})-1,I≤k.若G是k-临界h-边-连通但不(k 1)-临界h-边-连通,则记之为(h*,k*)λ.本文证明了:存在(h*,k*)λ图的充要条件是(1)1≤k≤[(h 1)/2],h≡0,1,2(mod 4);1≤k≤[(h-1)/2],h≡3(mod 4);或(2)k=h,G=Kk 1. 相似文献
4.
5.
6.
如果图G有一个生成子图使得这个生成子图的每一个分支都是3个点的路,则称G有P3-因子.本文证明了对任何一个2-边连通图G,只要G的边数能被3整除,则G的线图就有P3-因子。 相似文献
7.
对于给定的正整数 p 和 h,p≥h+1且 h≥4,本文给出了 p 阶临界 h棱连通图的最大棱数并且确定了所有达到最大棱数的 p 阶临界 h 棱连通图. 相似文献
8.
对于给定的正整数 p 和 h,p≥h+1且 h≥4,本文给出了 p 阶临界 h棱连通图的最大棱数并且确定了所有达到最大棱数的 p 阶临界 h 棱连通图. 相似文献
9.
图的最小特征值定义为图的邻接矩阵的最小特征值,是刻画图结构性质的一个重要代数参数. 在所有给定阶数的补图为2-点或2-边连通的图中, 刻画了最小特征值达到极小的唯一图, 并给出了这类图最小特征值的下界. 相似文献
10.
M.Kriesell证明了收缩临界5-连通图的平均度不超过24并猜想收缩临界5-连通图的平均度小于10.本文构造了一个反例证明M.Kriesell的猜想不成立并给出了收缩临界5-连通图平均度新的上界. 相似文献
11.
A graph G is said to be Critically n-line-connected if it is n-line-connected. but for each x∈G, λ (G - x )≤n- 1 .The following result is proved; Every critically n-line-connected graph contains at least two vertices of degree n, and then this lower bound is best possible as n≥ 3 . 相似文献
12.
13.
关于临界h棱连通图的最大棱数及最大图的结构(Ⅰ)——每点都与h度点相邻的最大临界h棱连通或h连通图的结构 总被引:2,自引:0,他引:2
徐俊明 《高校应用数学学报(A辑)》1988,(4)
图G称为临界h棱连通(或h连通)的,如果G是h棱连通(或h连通)的,但对每个x∈V(G),G-x不再是h棱连通(或h连通)的。对h≥4,本文确定了每点都与h度点相邻的所有具有最大棱数的临界h棱连通(或h连通)图的结构。 相似文献
14.
4连通图的可去边与4连通图的构造 总被引:2,自引:0,他引:2
本文引进了4连通图的可去边的概念,,并证明了4连通图G中不存在可去边的充要条件是G=C5或C6,同时给出了n阶4连通图的一个新的构造方法. 相似文献
15.
16.
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. 相似文献
17.
18.
19.
G是3-连通图,e是G中的一条边.若G-e是3-连通图的一个剖分,则称e是3-连通图的可去边.否则,e是G中不可去边.本给出3-连通3-正则图中生成树外可去边的分布情况及数目. 相似文献