共查询到19条相似文献,搜索用时 468 毫秒
1.
围长为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. 相似文献
2.
对于图方程 A( H) =n的讨论 ,重点是研究 A2 -图及 A3-图 H及其母图的性质 ,这就需要研究不同类型的 A3-图 .本文给出了不含悬挂点的 A3-图 相似文献
3.
4.
5.
6.
在文献[3]中介绍了一个新的图类-P3-支配图.这个图类包含所有的拟无爪图,因此也包含所有的无爪图.在本文中,我们证明了每一个点数至少是3的三角形连通的P3-支配图是哈密尔顿的,但有一个例外图K1,1,3.同时,我们也证明了k-连通的(k≥2)的P3-支配图是哈密尔顿的,如果an(G)≤k,但有两个例外图K1,1,3 and K2,3. 相似文献
7.
8.
9.
10.
黄振杰 《数学的实践与认识》2000,30(4)
一个图 G中含有的三个结点的导出连通子图的个数 S3( G)在网络可靠性中起着重要作用 .在同点数同边数图类中具有最大 S3( G)的图称为 3-优图 ,它所代表的网络是点故障概率接近 1时的最可靠网络 .本文在已有的结果上进一步证明补图为 a K3∪ b K2 ∪ K1和 a K3-x的图分别是各自图类中唯一的 3-优图 ;补图为 a K3∪ ( b-1 ) K2 ∪ 2 K1和 ( a-1 ) K3∪ b K2 ∪ P3的图是该图类中仅有的两个 3-优图 . 相似文献
11.
12.
13.
The clique graph K(G) of a given graph G is the intersection graph of the collection of maximal cliques of G. Given a family ℱ of graphs, the clique‐inverse graphs of ℱ are the graphs whose clique graphs belong to ℱ. In this work, we describe characterizations for clique‐inverse graphs of K3‐free and K4‐free graphs. The characterizations are formulated in terms of forbidden induced subgraphs. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 257–272, 2000 相似文献
14.
It was conjectured by Bouchet that every bidirected graph which admits a nowhere-zero κ flow will admit a nowhere-zero 6-flow. He proved that the conjecture is true when 6 is replaced by 216. Zyka improved the result with 6 replaced by 30. Xu and Zhang showed that the conjecture is true for 6-edge-connected graphs. And for 4-edge-connected graphs, Raspaud and Zhu proved it is true with 6 replaced by 4. In this paper, we show that Bouchet's conjecture is true with 6 replaced by 15 for 3-edge-connected graphs. 相似文献
15.
The P3-graph of a finite simple graph G is the graph whose vertices are the 3-vertex paths of G, with adjacency between two such paths whenever their union is a 4-vertex path or a 3-cycle. In this paper we show that connected fnite simple graphs G and H with isomorphic P3-graphs are either isomorphic or part of three exceptional families. We also characterize all isomorphisms between P3-graphs in terms of the original graphs. © 1997 John Wiley & Sons, Inc. J Graph Theory 26:35–51, 1997 相似文献
16.
In this paper, we study the edge clique cover number of squares of graphs. More specifically, we study the inequality θ(G2)θ(G) where θ(G) is the edge clique cover number of a graph G. We show that any graph G with at most θ(G) vertices satisfies the inequality. Among the graphs with more than θ(G) vertices, we find some graphs violating the inequality and show that dually chordal graphs and power-chordal graphs satisfy the inequality. Especially, we give an exact formula computing θ(T2) for a tree T. 相似文献
17.
A. A. Makhnev 《Mathematical Notes》1998,63(3):357-362
M. Numata described edge regular graphs without 3-stars. Allμ-subgraphs of these graphs are regular of the same valency. We prove that a connected graph without 3-stars all of whoseμ- subgraphs are regular of valencyα > 0 is either a triangular graph, or the Shläfli graph, or the icosahedron graph. 相似文献
18.
19.