6连通图中的可收缩边

Kriesell(2001年)猜想：如果κ连通图中任意两个相邻顶点的度的和至少是2[5κ/4]-1则图中有κ-可收缩边．本文证明每一个收缩临界6连通图中有两个相邻的度为6的顶点，由此推出该猜想对κ=6成立。     

Circumference and Pathwidth of Highly Connected Graphs

Birmele [J Graph Theory 2003] proved that every graph with circumference t has treewidth at most . Under the additional assumption of 2‐connectivity, such graphs have bounded pathwidth, which is a qualitatively stronger conclusion. Birmele's theorem was extended by Birmele et al. [Combinatorica 2007] who showed that every graph without k disjoint cycles of length at least t has treewidth . Our main result states that, under the additional assumption of ‐connectivity, such graphs have bounded pathwidth. In fact, they have pathwidth . Moreover, examples show that ‐connectivity is required for bounded pathwidth to hold. These results suggest the following general question: for which values of k and graphs H does every k‐connected H‐minor‐free graph have bounded pathwidth? We discuss this question and provide a few observations.     

Lower Bounds for Locally Highly Connected Graphs

We propose a conjecture regarding the lower bound for the number of edges in locally k-connected graphs and we prove it for \(k=2\). In particular, we show that every connected locally 2-connected graph is \(M_3\)-rigid. For the special case of surface triangulations, this fact was known before using topological methods. We generalize this result to all locally 2-connected graphs and give a purely combinatorial proof. Our motivation to study locally k-connected graphs comes from lower bound conjectures for flag triangulations of manifolds, and we discuss some more specific problems in this direction.     

Contractible Non-Edges in Triangle-Free Graphs

Thomassen has proved that every triangle-free k-connected graph contains a pair of adjacent vertices whose identification yields again a k-connected graph. We study the existence of a pair of nonadjacent vertices whose identification preserves k-connectivity. In particular, we present a reduction theorem for the class of all bipartite, k-connected graphs. Revised: January 7, 1999     

Contractible Cliques in k-Connected Graphs

Kawarabayashi proved that for any integer k≥4, every k-connected graph contains two triangles sharing an edge, or admits a k-contractible edge, or admits a k-contractible triangle. This implies Thomassen's result that every triangle-free k-connected graph contains a k-contractible edge. In this paper, we extend Kawarabayashi's technique and prove a more general result concerning k-contractible cliques. Xingxing Yu was partially supported by NSF grant DMS-0245530 and NSA grant MDA-904-03-1-0052.     

Treewidth of Cartesian Products of Highly Connected Graphs

The following theorem is proved: for all k‐connected graphs G and H each with at least n vertices, the treewidth of the cartesian product of G and H is at least . For , this lower bound is asymptotically tight for particular graphs G and H. This theorem generalizes a well‐known result about the treewidth of planar grid graphs.     

Contractible Small Subgraphs in k-connected Graphs

We prove that if G is highly connected, then either G contains a non-separating connected subgraph of order three or else G contains a small obstruction for the above conclusion. More precisely, we prove that if G is k-connected (with k ≥ 2), then G contains either a connected subgraph of order three whose contraction results in a k-connected graph (i.e., keeps the connectivity) or a subdivision of ${K_4^-}$ whose order is at most 6.     

Contractible Edges in 7-Connected Graphs

An edge of a k-connected graph is said to be a k-contractible edge, if its contraction yields again a k-connected graph. A noncomplete k-connected graph possessing no k-contractible edges is called contraction critical k-connected. Recently, Kriesell proved that every contraction critical 7-connected graph has two distinct vertices of degree 7. And he guessed that there are two vertices of degree 7 at distance one or two. In this paper, we give a proof to his conjecture. The work partially supported by NNSF of China(Grant number: 10171022)     

There Exist Highly Critically Connected Graphs of Diameter Three

Let κ(G) denote the (vertex) connectivity of a graph G. For ℓ≥0, a noncomplete graph of finite connectivity is called ℓ-critical if κ(G−X)=κ(G)−|X| for every X⊆V(G) with |X|≤ℓ. Mader proved that every 3-critical graph has diameter at most 4 and asked for 3-critical graphs having diameter exceeding 2. Here we give an affirmative answer by constructing an ℓ-critical graph of diameter 3 for every ℓ≥3.     

Contractible Edges in k-Connected Graphs with Some Forbidden Subgraphs

In 2001, Kawarabayashi proved that for any odd integer k ≥ 3, if a k-connected graph G is \({K^{-}_{4}}\) -free, then G has a k-contractible edge. He pointed out, by a counterexample, that this result does not hold when k is even. In this paper, we have proved the following two results on the subject: (1) For any even integer k ≥ 4, if a k-connected graph G is \({K_{4}^{-}}\) -free and d _G (x) + d _G (y) ≥ 2k + 1 hold for every two adjacent vertices x and y of V(G), then G has a k-contractible edge. (2) Let t ≥ 3, k ≥ 2t – 1 be integers. If a k-connected graph G is \({(K_{1}+(K_{2} \cup K_{1, t}))}\) -free and d _G (x) + d _G (y) ≥ 2k + 1 hold for every two adjacent vertices x and y of V(G), then G has a k-contractible edge.     

团复形是无圈的平面图是可伸缩图

许宝刚猜想:若图G的团复形是无圈的,则G为可伸缩图．本文证明了该猜想对平面图成立,即:若G是团复形为无圈的平面图,则G为可伸缩图．     

An Extremal Problem on Contractible Edges in 3-Connected Graphs

An edge e in a 3-connected graph G is contractible if the contraction G/e is still 3-connected. The existence of contractible edges is a very useful induction tool. Let G be a simple 3-connected graph with at least five vertices. Wu [7] proved that G has at most vertices that are not incident to contractible edges. In this paper, we characterize all simple 3-connected graphs with exactly vertices that are not incident to contractible edges. We show that all such graphs can be constructed from either a single vertex or a 3-edge-connected graph (multiple edges are allowed, but loops are not allowed) by a simple graph operation. Research partially supported by an ONR grant under grant number N00014-01-1-0917     

Weakly Connected Domination in Graphs

In the last 50 years, Graph theory has seen an explosive growth due to interaction with areas like computer science, electrical and communication engineering, Operations Research etc. Perhaps the fastest growing area within graph theory is the study of domination, the reason being its many and varied applications in such fields as social sciences, communication networks, algorithm designs, computational complexity etc. Henda C. Swart has rightly commented that the theory of domination in graphs is like a ‘growth industry’. There are several types of domination depending upon the nature of domination and the nature of the dominating set. In the following, we present weakly connected domination in connected graphs.     

Nonseparating Induced Cycles Consisting of Contractible Edges in k-Connected Graphs

It is proved that if G is a k-connected graph which does not contain K₄⁻, then G has an induced cycle C such that G – V(C) is (k − 2)-connected and either every edge of C is k-contractible or C is a triangle. This theorem is a generalization of some known theorems.     

Hamiltonian Connected Claw-Free Graphs

A well-known result by O. Ore is that every graph of order n with d(u)+d(v)n+1 for any pair of nonadjacent vertices u and v is hamiltonian connected (i.e., for every pair of vertices, there is a hamiltonian path joining them). In this paper, we show that every 3-connected claw-free graph G on at most 5–8 vertices is hamiltonian connected, where denotes the minimum degree in G. This result generalizes several previous results.Acknowledgments. The author would like to thank the referee for his important suggestions and careful corrections.Final version received: March 12, 2003Supported by the project of Nature Science Funds of China     

Connected Resolvability of Graphs

For an ordered set W = {w ₁, w ₂,..., w _k} of vertices and a vertex v in a connected graph G, the representation of v with respect to W is the k-vector r(v|W) = (d(v, w ₁), d(v, w ₂),... d(v, w _k)), where d(x, y) represents the distance between the vertices x and y. The set W is a resolving set for G if distinct vertices of G have distinct representations with respect to W. A resolving set for G containing a minimum number of vertices is a basis for G. The dimension dim(G) is the number of vertices in a basis for G. A resolving set W of G is connected if the subgraph 〈W〉 induced by W is a nontrivial connected subgraph of G. The minimum cardinality of a connected resolving set in a graph G is its connected resolving number cr(G). Thus 1 ≤ dim(G) ≤ cr(G) ≤ n?1 for every connected graph G of order n ≥ 3. The connected resolving numbers of some well-known graphs are determined. It is shown that if G is a connected graph of order n ≥ 3, then cr(G) = n?1 if and only if G = K _n or G = K _1,n?1. It is also shown that for positive integers a, b with a ≤ b, there exists a connected graph G with dim(G) = a and cr(G) = b if and only if $\left( {a,b} \right) \notin \left\{ {\left( {1,k} \right):k = 1\;{\text{or}}\;k \geqslant 3} \right\}$ Several other realization results are present. The connected resolving numbers of the Cartesian products G × K ₂ for connected graphs G are studied.     

图的连通因子

连通因子问题与Hamilton问题和信息网络有着密切的联系．1993年，首先由M.Kano就该问题在[6]中提出了许多问题和猜想，接下来他又在[16]中提出了一些猜想，本文就连通因子问题在过去十年的主要进展进行了回顾并提出了若干可进一步研究的问题和猜想．     

泛连通图的Faudree-Schelp定理和哈密尔顿连通图的Ore定理的注记

In this note more short proofs are given for Faudree-Schelp theorem and Ore theorem.     

On the Structure of Contractible Vertex Pairs in Chordal Graphs

An edge/non-edge in a k-connected graph is contractible if its contraction does not result in a graph of lower connectivity. We focus our study on contractible edges and non-edges in chordal graphs. Firstly, we characterize contractible edges in chordal graphs using properties of tree decompositions with respect to minimal vertex separators. Secondly, we show that in every chordal graph each non-edge is contractible. We also characterize non-edges whose contraction leaves a k-connected chordal graph.