共查询到20条相似文献,搜索用时 125 毫秒
1.
本文证明了若G是连通、局部连通的无爪图,则G是泛连通图的充要条件为G是3-连通图.这意味着H.J.Broersma和H.J.Veldman猜想成立. 相似文献
2.
图G中同构于K1,p的子图叫G的p-爪(p3).如果G中任意一个p-爪中1度顶点之间边的数目p-2,则称G为K1,p-受限图,它是无爪图(p=3时)的推广.本文证明了:连通、局部3-连通的K1,4-受限图是路可扩的. 相似文献
3.
4.
G是3-连通图,e是G中的一条边.若G-e是3-连通图的一个剖分,则称e是3-连通图的可去边.否则,e是G中不可去边.本给出3-连通3-正则图中生成树外可去边的分布情况及数目. 相似文献
5.
6.
7.
8.
《数学的实践与认识》2020,(1)
令G是一个简单连通图.如果连通图G被删除少于k条边后仍然保持连通,则称G是k-边连通的.基于图G或补图■的距离谱半径,距离无符号拉普拉斯谱半径,Wiener指数和Harary指数,提供了图G是k-边连通的新充分谱条件,从而建立了图的代数性质与结构性质之间的紧密联系. 相似文献
9.
张静 《高校应用数学学报(A辑)》2017,32(1)
给出连通的rectifiable空间是局部序列连通(或局部连通)的刻画,推广了拓扑群中的相应结果;利用rectifiable空间G中e的局部邻域基给出G是局部连通(或局部序列连通)的刻画;证明了若A是rectifiable空间G中的序列开子集,那么H=A是G的序列开rectifiable子空间. 相似文献
10.
点可迁图的限制边连通度 总被引:8,自引:0,他引:8
设S是连通图G的边子集.如果G-S不连通而且不含孤立点,那么称S是G的一个限制边割.G中所有限制边割中最小边数称为G的限制边连通度,记为′(G).限制边连通度是对传统边连通度的推广,而且是计算机互连网络容错性的一个重要度量.点可迁图是一类重要的网络模型.本文证明了如下结论
设G是连通的点可迁图.如果G的点数n4,而且点度k2,那么或者′(G)=2k-2,或者n是偶数,G含三角形且存在整数m2,使得k′(G)=n/m2k-3. 相似文献
11.
Tutte introduced the theory of nowhere zero flows and showed that a plane graph G has a face k-coloring if and only if G has a nowhere zero A-flow, for any Abelian group A with |A|≥k. In 1992, Jaeger et al. [9] extended nowhere zero flows to group connectivity of graphs: given an orientation D of a graph G, if for any b:V(G)?A with ∑v∈V(G)b(v)=0, there always exists a map f:E(G)?A−{0}, such that at each v∈V(G), in A, then G is A-connected. Let Z3 denote the cyclic group of order 3. In [9], Jaeger et al. (1992) conjectured that every 5-edge-connected graph is Z3-connected. In this paper, we proved the following.
(i)
Every 5-edge-connected graph is Z3-connected if and only if every 5-edge-connected line graph is Z3-connected. (ii)
Every 6-edge-connected triangular line graph is Z3-connected. (iii)
Every 7-edge-connected triangular claw-free graph is Z3-connected.
12.
Tutte conjectured that every 4-edge-connected graph admits a nowhere-zero Z
3-flow and Jaeger et al. [Group connectivity of graphs–a nonhomogeneous analogue of nowhere-zero flow properties, J. Combin.
Theory Ser. B 56 (1992) 165-182] further conjectured that every 5-edge-connected graph is Z
3-connected. These two conjectures are in general open and few results are known so far. A weaker version of Tutte’s conjecture
states that every 4-edge-connected graph with each edge contained in a circuit of length at most 3 admits a nowhere-zero Z
3-flow. Devos proposed a stronger version problem by asking if every such graph is Z
3-connected. In this paper, we first answer this later question in negative and get an infinite family of such graphs which
are not Z
3-connected. Moreover, motivated by these graphs, we prove that every 6-edge-connected graph whose edge set is an edge disjoint
union of circuits of length at most 3 is Z
3-connected. It is a partial result to Jaeger’s Z
3-connectivity conjecture.
Received: May 23, 2006. Final version received: January 13, 2008 相似文献
13.
Let G be a 2-edge-connected simple graph on n ≥ 14 vertices, and let A be an abelian group with the identity element 0. If a graph G* is obtained by repeatedly contracting nontrivial A-connected subgraphs of G until no such a subgraph left, we say that G can be A-reduced to G*. In this paper, we prove that if for every ${uv\not\in E(G), |N(u) \cup N(v)| \geq \lceil \frac{2n}{3} \rceil}$ , then G is not Z 3-connected if and only if G can be Z 3-reduced to one of ${\{C_3,K_4,K_4^-, L\}}$ , where L is obtained from K 4 by adding a new vertex which is joined to two vertices of K 4. 相似文献
14.
A graph G is locally n-connected, n ≥ 1, if the subgraph induced by the neighborhood of each vertex is n-connected. We prove that every connected, locally 2-connected graph containing no induced subgraph isomorphic to K1,3 is panconnected. 相似文献
15.
A graphG is locallyn-connected,n≧1, if the subgraph induced by the neighborhood of each vertex isn-connected. It is shown that every connected, locally 3-connected graph containing no induced subgraph isomorphic toK(1, 3) is hamiltonian-connected. 相似文献
16.
It has previously been shown that if M is a maximum matching in a 3-connected graph G, other than K4, then M contains at least one contractible edge of G. In this paper, we give a constructive characterization of the 3-connected graphs G having a maximum matching containing only one contractible edge of G. 相似文献
17.
Zhou Huai-Lu 《Journal of Graph Theory》1989,13(6):651-656
We prove the following conjecture of Broersma and Veldman: A connected, locally k-connected K1,3-free graph is k-hamiltonian if and only if it is (k + 2)-connected (K ? 1). 相似文献
18.
Independently, Claytor [Ann. Math. 35 (1934), 809–835] and Thomassen [Combinatorica 24 (2004), 699–718] proved that a 2-connected, compact, locally connected metric space is homeomorphic to a subset of the sphere
if and only if it does not contain K
5 or K
3;3. The “thumbtack space” consisting of a disc plus an arc attaching just at the centre of the disc shows the assumption of
2-connectedness cannot be dropped. In this work, we introduce “generalized thumbtacks” and show that a compact, locally connected
metric space is homeomorphic to a subset of the sphere if and only if it does not contain K
5, K
3;3, or any generalized thumbtack, or the disjoint union of a sphere and a point. 相似文献
19.
We investigate graphs G such that the line graph L(G) is hamiltonian connected if and only if L(G) is 3-connected, and prove that if each 3-edge-cut contains an edge lying in a short cycle of G, then L(G) has the above mentioned property. Our result extends Kriesell’s recent result in [M. Kriesell, All 4-connected line graphs of claw free graphs are hamiltonian-connected, J. Combin. Theory Ser. B 82 (2001) 306-315] that every 4-connected line graph of a claw free graph is hamiltonian connected. Another application of our main result shows that if L(G) does not have an hourglass (a graph isomorphic to K5−E(C4), where C4 is an cycle of length 4 in K5) as an induced subgraph, and if every 3-cut of L(G) is not independent, then L(G) is hamiltonian connected if and only if κ(L(G))≥3, which extends a recent result by Kriesell [M. Kriesell, All 4-connected line graphs of claw free graphs are hamiltonian-connected, J. Combin. Theory Ser. B 82 (2001) 306-315] that every 4-connected hourglass free line graph is hamiltonian connected. 相似文献
20.
The supereulerian graph problem, raised by Boesch et al. (J Graph Theory 1:79–84, 1977), asks when a graph has a spanning
eulerian subgraph. Pulleyblank showed that such a decision problem, even when restricted to planar graphs, is NP-complete.
Jaeger and Catlin independently showed that every 4-edge-connected graph has a spanning eulerian subgraph. In 1992, Zhan showed
that every 3-edge-connected, essentially 7-edge-connected graph has a spanning eulerian subgraph. It was conjectured in 1995
that every 3-edge-connected, essentially 5-edge-connected graph has a spanning eulerian subgraph. In this paper, we show that
if G is a 3-edge-connected, essentially 4-edge-connected graph and if for every pair of adjacent vertices u and v, d
G
(u) + d
G
(v) ≥ 9, then G has a spanning eulerian subgraph. 相似文献