Minimum degree condition for a graph to be knitted

For a positive integer $k$, a graph is $k$-knitted if for each subset $S$ of $k$ vertices, and every partition of $S$ into (disjoint) parts $S_1,\dots ,S_t$ for some $t\ge 1$, one can find disjoint connected subgraphs $C_1,\dots ,C_t$ such that $C_i$ contains $S_i$ for each $i\in \left[t\right]?\{1,2,\dots ,t\}$. In this article, we show that if the minimum degree of an $n$-vertex graph $G$ is at least $n∕2+k∕2?1$ when $n\ge 2k+3$, then $G$ is $k$-knitted. The minimum degree is sharp. As a corollary, we obtain that $k$-contraction-critical graphs are $?\frac{k}{8}?$-connected.     

A lower bound for the circumference of a graph

Let G=(V, E) be a block of order n, different from K_n. Let m=min {d(x)+d(y): [x, y]?E}. We show that if m?n then G contains a cycle of length at least m.     

A sufficient condition for equality of edge-connectivity and minimum degree of a graph

Let G be a connected graph of order p ≥ 2, with edge-connectivity κ₁(G) and minimum degree δ(G). It is shown her ethat in order to obtain the equality κ₁(G) = δ(G), it is sufficient that, for each vertex x of minimum degree in G, the vertices in the neighbourhood N(x) of x have sufficiently large degree sum. This result implies a previous result of Chartrand, which required that δ(G) ≥ [p/2].     

A minimum degree condition forcing complete graph immersion

An immersion of a graph H into a graph G is a one-to-one mapping f: V (H) → V (G) and a collection of edge-disjoint paths in G, one for each edge of H, such that the path P _uv corresponding to edge uv has endpoints f(u) and f(v). The immersion is strong if the paths P _uv are internally disjoint from f(V (H)). It is proved that for every positive integer Ht, every simple graph of minimum degree at least 200t contains a strong immersion of the complete graph K _t . For dense graphs one can say even more. If the graph has order n and has 2cn ² edges, then there is a strong immersion of the complete graph on at least c ² n vertices in G in which each path P _uv is of length 2. As an application of these results, we resolve a problem raised by Paul Seymour by proving that the line graph of every simple graph with average degree d has a clique minor of order at least cd ^3/2, where c>0 is an absolute constant. For small values of t, 1≤t≤7, every simple graph of minimum degree at least t?1 contains an immersion of K _t (Lescure and Meyniel [13], DeVos et al. [6]). We provide a general class of examples showing that this does not hold when t is large.     

A degree condition for a graph to have [a,b]-factors

Let G be a graph of order n, and let a and b be integers such that 1 ≤ a < b. We show that G has an [a, b]-factor if δ(G) ≥ a, n ≥ 2a + b + and max {d_G(u), d_G(v) ≥ for any two nonadjacent vertices u and v in G. This result is best possible, and it is an extension of T. Iida and T. Nishimura's results (T. Iida and T. Nishimura, An Ore-type condition for the existence of k-factors in graphs, Graphs and Combinat. 7 (1991), 353–361; T. Nishimura, A degree condition for the existence of k-factors, J. Graph Theory 16 (1992), 141–151). about the existence of a k-factor. As an immediate consequence, it shows that a conjecture of M. Kano (M. Kano, Some current results and problems on factors of graphs, Proc. 3rd China–USA International Conference on Graph Theory and Its Application, Beijing (1993). about connected [a, b]-factors is incorrect. © 1998 John Wiley & Sons, Inc. J Graph Theory 27: 1–6, 1998     

包含k-树图的毁裂度条件

连通图G的一个k-树是指图G的一个最大度至多是k的生成树.对于连通图G来说,其毁裂度定义为r(G)=max{ω(G-X)-|X|-m(G-X)|X■V(G),ω(G-X)1}其中ω(G-X)和m(G-X)分别表示G-X中的分支数目和最大分支的阶数.本文结合毁裂度给出连通图G包含一个k-树的充分条件;利用图的结构性质和毁裂度的关系逐步刻画并给出图G包含一个k-树的毁裂度条件.     

The strongest monotone degree condition for n-connectedness of a graph

It is shown that Bondy's degree condition for n-connectedness of a graph is the strongest monotone degree condition for forcibly n-connected graphic sequences.     

最大度为6的平面图为第一类的一个新充分条件

本文证明了:若一个平面图G不含带弦的6-圈,则G是第一类的.这部分地证实了Vizing的关于平面图边染色的一个猜想.     

The circumference of the square of a connected graph

The celebrated result of Fleischner states that the square of every 2-connected graph is Hamiltonian. We investigate what happens if the graph is just connected. For every n ≥ 3, we determine the smallest length c(n) of a longest cycle in the square of a connected graph of order n and show that c(n) is a logarithmic function in n. Furthermore, for every c ≥ 3, we characterize the connected graphs of largest order whose square contains no cycle of length at least c.     

A median-type condition for graph tiling

Komlós (2000) determined the asymptotically optimal minimum degree condition for covering a given proportion of vertices of a host graph by vertex-disjoint copies of a fixed graph. We show that the minimum degree condition can be relaxed in the sense that we require only a given fraction of vertices to have the prescribed degree.     

A sufficient condition for a graph to be hamiltonian

Those non-hamiltonian graphsG withn vertices are characterized, which satisfy the Ore-type degree-conditiond(x)+d(y)n–2 for each pairx,yM of different nonadjacent vertices whereM consists of two vertices ofG. As an application a theorem on hamiltonian connectivity of graphs is given. Furthermore, a condition is presented which is sufficient for the existence of a covering of a graph by two disjoint paths with prescribed set of startpoints and prescribed set of endpoints. A class of graphs is described which have no covering of this kind.     

On the circumference of a graph and its complement

Let G be a graph of order n and circumference c(G). Let be the complement of G. We prove that and show sharpness of this bound.     

A degree condition for the existence of k-factors

Let k be an integer such that ≦, and let G be a connected graph of order n with ≦, kn even, and minimum degree at least k. We prove that if G satisfies max(deg(u), deg(v)) ≦ n/2 for each pair of nonadjacent vertices u, v in G, then G has a k-factor.     

A sufficient condition for a bipartite graph to have a k-factor

P. Katerinis obtained a sufficient condition for the existence of a 2-factor in a bipartite graph, in the spirit of Hall's theorem. We show a sufficient condition for the existence of a k-factor in a bipartite graph, as a generalization of Katerinis's theorem and Hall's theorem.     

On the degree distance of a graph

If G is a connected graph with vertex set V, then the degree distance of G, D^′(G), is defined as , where degw is the degree of vertex w, and d(u,v) denotes the distance between u and v. We prove the asymptotically sharp upper bound for graphs of order n and diameter d. As a corollary we obtain the bound for graphs of order n. This essentially proves a conjecture by Tomescu [I. Tomescu, Some extremal properties of the degree distance of a graph, Discrete Appl. Math. (98) (1999) 159-163].     

A sufficient condition for a regular graph to be class 1

The core GΔ of a simple graph G is the subgraph induced by the vertices of maximum degree. It is well known that the Petersen graph is not 1-factorizable and has property that the core of the graph obtained from it by removing one vertex has maximum degree 2. In this paper, we prove the following result. Let G be a regular graph of even order with d(G) ≥ 3. Suppose that G contains a vertex ν such that the core of G\ν has maximum degree 2. If G is not the Petersen graph, then G is 1-factorizable. © 1993 John Wiley & Sons, Inc.