首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 296 毫秒
1.
本文证明了若G是连通、局部连通的无爪图,则G是泛连通图的充要条件为G是3-连通图.这意味着H.J.Broersma和H.J.Veldman猜想成立.  相似文献   

2.
3.
4.
设G是一个n阶k连通图(k  相似文献   

5.
h连通图中非临界点的个数   总被引:1,自引:0,他引:1  
周红卫 《应用数学》1995,8(2):127-134
设G是h连通的简单非完全图,v中G的顶点,若k(G-v)≥k(G),则称v是G的非临界点,关于G中非临界点的个数,Veldman和苏健基分别给定了在不同条件下的下界,本文推广了他们的结果,得到了更一般的下界。  相似文献   

6.
张树生 《数学杂志》1994,14(2):287-288
关于三圈连通标号图的计数公式张树生江西宁都固厚中学本文所指的图者是无向简单图。如果一个图恰好包含有m个初级圈,那么就说这个图恰好包含有m个单个的圈。Harary在[1]中提出了给定圈的个数的连通标号圈的计数问题。Renyi在[2]中解决了单圈边通标号...  相似文献   

7.
蒋红星  苏健基 《数学研究》2002,35(2):187-193
给出了极小拟5连通图有围长大于或等于4的极小拟(k)+1连通图的最小度。  相似文献   

8.
本文得到了任意两个连通循环图是(?)d(?)m同构的充要条件,并且还得到两个连通循环图是(?)d(?)m同构的另一必要条件。  相似文献   

9.
本文讨论一般含1-因子连通图的n次幂中边不交1-因子的个数.从而证明了L.Nebesky(1984)猜想对含1-因子图成立.  相似文献   

10.
周永生 《应用数学》1993,6(3):262-266
本文得到了奇数度循环图C_n是连通的充要条件及C_n不连通的情形.证明了三度连通循环图C_n同构于C_n<1,n/2>或C_n<2,n/2>.这一结果颇有意义.  相似文献   

11.
Removable Edges in Longest Cycles of 4-Connected Graphs   总被引:3,自引:0,他引:3  
Let G be a 4-connected graph. For an edge e of G, we do the following operations on G: first, delete the edge e from G, resulting the graph Ge; second, for all vertices x of degree 3 in Ge, delete x from Ge and then completely connect the 3 neighbors of x by a triangle. If multiple edges occur, we use single edges to replace them. The final resultant graph is denoted by Ge. If Ge is 4-connected, then e is called a removable edge of G. In this paper we obtain some results on removable edges in a longest cycle of a 4-connected graph G. We also show that for a 4-connected graph G of minimum degree at least 5 or girth at least 4, any edge of G is removable or contractible.Acknowledgment. The authors are greatly indebted to a referee for his valuable suggestions and comments, which are very helpful to improve the proof of our main result Lemma 3.3.Research supported by National Science Foundation of China AMS subject classification (2000): 05C40, 05C38, 05C75Final version received: March 10, 2004  相似文献   

12.
An edge e of a k-connected graph G is said to be a removable edge if G?e is still k-connected. A k-connected graph G is said to be a quasi (k+1)-connected if G has no nontrivial k-separator. The existence of removable edges of 3-connected and 4-connected graphs and some properties of quasi k-connected graphs have been investigated [D.A. Holton, B. Jackson, A. Saito, N.C. Wormale, Removable edges in 3-connected graphs, J. Graph Theory 14(4) (1990) 465-473; H. Jiang, J. Su, Minimum degree of minimally quasi (k+1)-connected graphs, J. Math. Study 35 (2002) 187-193; T. Politof, A. Satyanarayana, Minors of quasi 4-connected graphs, Discrete Math. 126 (1994) 245-256; T. Politof, A. Satyanarayana, The structure of quasi 4-connected graphs, Discrete Math. 161 (1996) 217-228; J. Su, The number of removable edges in 3-connected graphs, J. Combin. Theory Ser. B 75(1) (1999) 74-87; J. Yin, Removable edges and constructions of 4-connected graphs, J. Systems Sci. Math. Sci. 19(4) (1999) 434-438]. In this paper, we first investigate the relation between quasi connectivity and removable edges. Based on the relation, the existence of removable edges in k-connected graphs (k?5) is investigated. It is proved that a 5-connected graph has no removable edge if and only if it is isomorphic to K6. For a k-connected graph G such that end vertices of any edge of G have at most k-3 common adjacent vertices, it is also proved that G has a removable edge. Consequently, a recursive construction method of 5-connected graphs is established, that is, any 5-connected graph can be obtained from K6 by a number of θ+-operations. We conjecture that, if k is even, a k-connected graph G without removable edge is isomorphic to either Kk+1 or the graph Hk/2+1 obtained from Kk+2 by removing k/2+1 disjoint edges, and, if k is odd, G is isomorphic to Kk+1.  相似文献   

13.
Contraction of an edge e merges its end points into a new single vertex, and each neighbor of one of the end points of e is a neighbor of the new vertex. An edge in a k-connected graph is contractible if its contraction does not result in a graph with lesser connectivity; otherwise the edge is called non-contractible. In this paper, we present results on the structure of contractible edges in k-trees and k-connected partial k-trees. Firstly, we show that an edge e in a k-tree is contractible if and only if e belongs to exactly one (k + 1) clique. We use this characterization to show that the graph formed by contractible edges is a 2-connected graph. We also show that there are at least |V(G)| + k − 2 contractible edges in a k-tree. Secondly, we show that if an edge e in a partial k-tree is contractible then e is contractible in any k-tree which contains the partial k-tree as an edge subgraph. We also construct a class of contraction critical 2k-connected partial 2k-trees.  相似文献   

14.
Let G be a 5-connected graph. For an edge e of G, we do the following operations on G: first, delete the edge e from G, resulting the graph G?e; second, for each vertex x of degree 4 in G?e, delete x from G?e and then completely connect the 4 neighbors of x by K 4. If multiple edges occur, we use single edge to replace them. The final resultant graph is denoted by G ? e. If G ? e is still 5-connected, then e is called a removable edge of G. In this paper, we investigate the distribution of removable edges in a cycle of a 5-connected graph. And we give examples to show some of our results are best possible in some sense.  相似文献   

15.
An edge e of a 3-connected graph G is said to be removable if G - e is a subdivision of a 3-connected graph. If e is not removable, then e is said to be nonremovable. In this paper, we study the distribution of removable edges in 3-connected graphs and prove that a 3-connected graph of order n ≥ 5 has at most [(4 n — 5)/3] nonremovable edges.  相似文献   

16.
Let G be a simple 3-connected graph. An edge e of G is essential if neither the deletion G\ e nor the contraction G/e is both simple and 3-connected. In this study, we show that all 3-connected graphs with k(k ≥ 2) non-essential edges can be obtained from a wheel by three kinds of operations which defined in the paper.  相似文献   

17.
The Erdős-Sós conjecture says that a graph G on n vertices and number of edges e(G) > n(k− 1)/2 contains all trees of size k. In this paper we prove a sufficient condition for a graph to contain every tree of size k formulated in terms of the minimum edge degree ζ(G) of a graph G defined as ζ(G) = min{d(u) + d(v) − 2: uvE(G)}. More precisely, we show that a connected graph G with maximum degree Δ(G) ≥ k and minimum edge degree ζ(G) ≥ 2k − 4 contains every tree of k edges if d G (x) + d G (y) ≥ 2k − 4 for all pairs x, y of nonadjacent neighbors of a vertex u of d G (u) ≥ k.  相似文献   

18.
A k-edge-weighting w of a graph G is an assignment of an integer weight, w(e) ∈ {1,…,k}, to each edge e. An edge-weighting naturally induces a vertex coloring c by defining c(u) = Σ eu w(e) for every uV (G). A k-edge-weighting of a graph G is vertex-coloring if the induced coloring c is proper, i.e., c(u) ≠ c(v) for any edge uvE(G). When k ≡ 2 (mod 4) and k ⩾ 6, we prove that if G is k-colorable and 2-connected, δ(G) ⩾ k − 1, then G admits a vertex-coloring k-edge-weighting. We also obtain several sufficient conditions for graphs to be vertex-coloring k-edge-weighting.   相似文献   

19.
We verify two special cases of Thomassen’s conjecture of 1976 stating that every longest cycle in a 3-connected graph contains a chord.We prove that Thomassen’s conjecture is true for two classes of 3-connected graphs that have a bounded number of removable edges on or off a longest cycle. Here an edge e of a 3-connected graph G is said to be removable if Ge is still 3-connected or a subdivision of a 3-connected (multi)graph.We give examples to showthat these classes are not covered by previous results.  相似文献   

20.
Contractible edges in triangle-free graphs   总被引:2,自引:0,他引:2  
An edge of a graph is calledk-contractible if the contraction of the edge results in ak-connected graph. Thomassen [5] proved that everyk-connected graph of girth at least four has ak-contractible edge. In this paper, we study the distribution ofk-contractible edges in triangle-free graphs and show the following: Whenk≧2, everyk-connected graph of girth at least four and ordern≧3k, hasn+(3/2)k 2-3k or morek-contractible edges.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号