排序方式: 共有46条查询结果,搜索用时 0 毫秒
1.
一个边割被称为圈边割,如果该边割能分离图的两个不同圈.如果一个图有圈边割,称该图为圈边可分离的.一个圈边可分离图G的最小圈边割的阶数被称为圈边连通度,记作cλ(G).定义:ζ(G)=min{w(X)|X导出G的最短圈},其中w(X)为端点分别在X和V(G)-X中的边的数目.如果一个圈边可分离图G使得cλ(G)=ζ(G)成立,称该图是圈边最优的.Tian和Meng在文章[11]以及Yang et al在文章[15]中研究了两种不同的双轨道图的圈边最优性.本文我们将研究具有两个同阶轨道的双轨道图的圈边连通度. 相似文献
2.
Ramesh Prasad Panda 《代数通讯》2018,46(7):3182-3197
In this paper, the minimum degree of power graphs of certain cyclic groups, abelian p-groups, dihedral groups and dicyclic groups are obtained. It is ascertained that the edge-connectivity and minimum degree of power graphs are equal, and consequently, the minimum disconnecting sets of power graphs of the aforementioned groups are determined. In order to investigate the equality of connectivity and minimum degree of power graphs, certain necessary conditions for finite groups and a necessary and su?cient condition for finite cyclic groups are obtained. Moreover, the equality is discussed for the power graphs of abelian p-groups, dihedral groups and dicyclic groups. 相似文献
3.
WANG Yingqian Department of Mathematics Zhejiang Normal University Jinhua China 《中国科学A辑(英文版)》2006,49(6):791-799
The third edge-connectivity λ3(G) of a graph G is defined as the minimum cardinality over all sets of edges, if any, whose deletion disconnects G and each component of the resulting graph has at least 3 vertices. An upper bound has been established for λ3(G) whenever λ3(G) is well-defined. This paper first introduces two combinatorial optimization concepts, that is, maximality and superiority, of λ3(G), and then proves the Ore type sufficient conditions for G to be maximally and super third edge-connected. These concepts and results are useful in network reliability analysis. 相似文献
4.
We prove that, for any given vertex ν* in a series-parallel graph G, its edge set can be partitioned into κ = min{κ′(G) + 1, δ(G)} subsets such that each subset covers all the vertices of G possibly except for ν*, where δ(G) is the minimum degree of G and κ′(G) is the edge-connectivity of G. In addition, we show that the results in this paper are best possible and a polynomial time algorithm can be obtained for
actually finding such a partition by our proof. 相似文献
5.
Plesnik in 1972 proved that an (m - 1)-edge connected m-regular graph of even order has a 1-factor containing any given edge and has another 1-factor excluding any given m - 1 edges. Alder et al. in 1999 showed that if G is a regular (2n + 1)-edge-connected bipartite graph, then G has a 1-factor containing any given edge and excluding any given matching of size n. In this paper we obtain some sufficient conditions related to the edge-connectivity for an n-regular graph to have a k-factor containing a set of edges and (or) excluding a set of edges, where 1 ≤ k ≤n/2. In particular, we generalize Plesnik's result and the results obtained by Liu et al. in 1998, and improve Katerinis' result obtained 1993. Furthermore, we show that the results in this paper are the best possible. 相似文献
6.
The bounded edge-connectivity λk(G) of a connected graph G with respect to is the minimum number of edges in G whose deletion from G results in a subgraph with diameter larger than k and the edge-persistence D+(G) is defined as λd(G)(G), where d(G) is the diameter of G. This paper considers the Cartesian product G1×G2, shows λk1+k2(G1×G2)≥λk1(G1)+λk2(G2) for k1≥2 and k2≥2, and determines the exact values of D+(G) for G=Cn×Pm, Cn×Cm, Qn×Pm and Qn×Cm. 相似文献
7.
Zoltán Szigeti 《Discrete Applied Mathematics》2008,156(7):1011-1018
Let G=(V+s,E) be a 2-edge-connected graph with a designated vertex s. A pair of edges rs,st is called admissible if splitting off these edges (replacing rs and st by rt) preserves the local edge-connectivity (the maximum number of pairwise edge disjoint paths) between each pair of vertices in V. The operation splitting off is very useful in graph theory, it is especially powerful in the solution of edge-connectivity augmentation problems as it was shown by Frank [Augmenting graphs to meet edge-connectivity requirements, SIAM J. Discrete Math. 5(1) (1992) 22-53]. Mader [A reduction method for edge-connectivity in graphs, Ann. Discrete Math. 3 (1978) 145-164] proved that if d(s)≠3 then there exists an admissible pair incident to s. We generalize this result by showing that if d(s)?4 then there exists an edge incident to s that belongs to at least ⌊d(s)/3⌋ admissible pairs. An infinite family of graphs shows that this bound is best possible. We also refine a result of Frank [On a theorem of Mader, Discrete Math. 101 (1992) 49-57] by describing the structure of the graph if an edge incident to s belongs to no admissible pairs. This provides a new proof for Mader's theorem. 相似文献
8.
Shengzhang Ren 《Discrete Mathematics》2011,(16):1666
It is shown that every generalized fullerene graph G with 13 pentagons is 2-extendable, a brick, and cyclically 5-edge-connected, i.e., that G cannot be separated into two components, each containing a cycle, by deletion of fewer than five edges. New lower bound on the number of perfect matchings in such graphs are also established. 相似文献
9.
Sufficient Conditions for Maximally Edge-connected and Super-edge-connected Digraphs Depending on the Size 下载免费PDF全文
Let D be a finite and simple digraph with vertex set V (D). The minimum degree δ of a digraph D is defined as the minimum value of its out-degrees and its in-degrees. If D is a digraph with minimum degree δ and edge-connectivity λ, then λ ≤ δ. A digraph is maximally edge-connected if λ=δ. A digraph is called super-edge-connected if every minimum edge-cut consists of edges incident to or from a vertex of minimum degree. In this note we show that a digraph is maximally edge-connected or super-edge-connected if the number of arcs is large enough. 相似文献
10.
LIU Guizhen DENG Xiaotie & XU Changqing School of Mathematics System Science Shandong University Jinan China Department of Computer Science City University of Hong Kong Kowloon Hong Kong China Department of Applied Mathematics Hebei University of Technology Tianjin China 《中国科学A辑(英文版)》2006,(8)
We prove that, for any given vertexν* in a series-parallel graph G, its edge set can be partitioned into k= min{k′(G) 1,δ(G)} subsets such that each subset covers all the vertices of G possibly except forν*, whereδ(G) is the minimum degree of G and k′(G) is the edge-connectivity of G. In addition, we show that the results in this paper are best possible and a polynomial time algorithm can be obtained for actually finding such a partition by our proof. 相似文献