大次和的1－坚韧图中的最长圈

给一个图Ｇ，定义，是Ｇ的无关集，是Ｇ中使的无关集，本文证明了：设Ｇ是ｎ阶１－坚韧图，如果σｓ３≥ｎ。，则Ｇ包含长度至少为ｍｉｎ的圈。这个结果推广了若干已知结果，也解决了Ｂｒｏｅｒｓｍａ－Ｈｅｕｖｅｌ－Ｖｅｌｄｍａｎ所提猜想的一个特例．     

Longest Paths and Longest Cycles in Graphs with Large Degree Sums

 Let p(G) and c(G) denote the number of vertices in a longest path and a longest cycle, respectively, of a finite, simple graph G. Define σ₄(G)=min{d(x ₁)+d(x ₂)+ d(x ₃)+d(x ₄) | {x ₁,…,x ₄} is independent in G}. In this paper, the difference p(G)−c(G) is considered for 2-connected graphs G with σ₄(G)≥|V(G)|+3. Among others, we show that p(G)−c(G)≤2 or every longest path in G is a dominating path. Received: August 28, 2000 Final version received: May 23, 2002     

Degree Sums and Covering Cycles

It is shown that if in a simple graph G of order n the sum of degrees of any three pairwise non-adjacent vertices is at least n, then there are two cycles (or one cycle and an edge or a vertex) of GF that contain all the vertices. © 1995 John Wiley & Sons, Inc.     

Degree Sums and Path-Factors in Graphs

 Let G be a connected graph of order n and suppose that n=∑ _{i =1} ^k n _i , where n _i ≥2 are integers. In this paper we give some sufficient conditions in terms of degree sums to ensure that G contains a spanning subgraph consisting of vertex disjoint paths of orders n ₁,n ₂,…,n _k . Received: June 30, 1999 Final version received: July 31, 2000     

图的度和与扩路

本文讨论了两顶点的度和与路可扩之间的关系,得到了如下结果:设G是n阶图,如果G中任意一对不相邻的顶点u,v满足d(u)+d(v)≥n+n/k(2≤k≤n-2),则G中任意一个满足k+1≤|P|相似文献   

Cycles in Graphs with Prescribed Stability Number and Connectivity

D. Amar, I. Fournier, A. Germa, R. Haggkvist, and C. Thomassen conjectured that the vertices of a k-connected graph with stability number α can be covered by α/k cycles. We prove this conjecture.     

3-连通、高次和坚韧图周长的估计(I)

设G是一个n阶3-连通图,周长为C(G),独立数为α,若G是1-坚韧的,且σ     

度和与图中具有给定阶数的点不交的路

设G是一个n阶图，n=∑^ki=1ni，其中,ni≥2(i=1,2,…，k）是整数。我们利用度和给出图G中存在n1,n2，…，nk阶点不交路的充分条件。     

Pairs of Disjoint Dominating Sets and the Minimum Degree of Graphs

For a connected graph G of order n and minimum degree δ we prove the existence of two disjoint dominating sets D ₁ and D ₂ such that, if δ ≥ 2, then ${|D_1\cup D_2|\leq \frac{6}{7}n}$ unless G = C ₄, and, if δ ≥ 5, then ${|D_1\cup D_2|\leq 2\frac{1+\ln(\delta+1)}{\delta+1}n}$ . While for the first estimate there are exactly six extremal graphs which are all of order 7, the second estimate is asymptotically best-possible.     

最小度不小于3的图的圈长问题

Bondy和Vince曾证明最小度不小于3的图包含两个长度相差为1或者2的圈,这个结果回答了ErdSs提出的问题．Haggkvist和scott证明了除肠外,所有的3-正则图都包含两个长度相差2的圈．通过不同的方法,我们得到了下面的结论：除了每个端块都是硒的图外,所有最小度不小于3的图都包含两个长度相差2的圈．     

A Minimum Degree Result for Disjoint Cycles and Forests in Graphs

F on s edges and k disjoint cycles. The main result is the following theorem. Let F be a forest on s edges without isolated vertices and let G be a graph of order at least with minimum degree at least , where k, s are nonnegative integers. Then G contains the disjoint union of the forest F and k disjoint cycles. This theorem provides a common generalization of previous results of Corrádi & Hajnal [4] and Brandt [3] who considered the cases (cycles only) and (forests only), respectively. Received: October 13, 1995     

Dominating Functions and Graphs

A graph is called dominating if its vertices can be labelledwith integers in such a way that for every function : thegraph contains a ray whose sequence of labels eventually exceeds. We obtain a characterization of these graphs by producinga small family of dominating graphs with the property that everydominating graph must contain some member of the family.     

Global Connectivity And Expansion: Long Cycles and Factors In f-Connected Graphs

Given a function f : ℕ→ℝ, call an n-vertex graph f-connected if separating off k vertices requires the deletion of at least f(k) vertices whenever k≤(n−f(k))/2. This is a common generalization of vertex connectivity (when f is constant) and expansion (when f is linear). We show that an f-connected graph contains a cycle of length linear in n if f is any linear function, contains a 1-factor and a 2-factor if f(k)≥2k+1, and contains a Hamilton cycle if f(k)≥2(k+1)². We conjecture that linear growth of f suffices to imply hamiltonicity.     

Moore Graphs and Cycles Are Extremal Graphs for Convex Cycles

Let denote the number of convex cycles of a simple graph G of order n, size m, and girth . It is proved that and that equality holds if and only if G is an even cycle or a Moore graph. The equality also holds for a possible Moore graph of diameter 2 and degree 57 thus giving a new characterization of Moore graphs.     

On a Sharp Degree Sum Condition for Disjoint Chorded Cycles in Graphs

Let r and s be nonnegative integers, and let G be a graph of order at least 3r + 4s. In Bialostocki et al. (Discrete Math 308:5886–5890, 2008), conjectured that if the minimum degree of G is at least 2r + 3s, then G contains a collection of r + s vertex-disjoint cycles such that s of them are chorded cycles, and they showed that the conjecture is true for r = 0, s = 2 and for s = 1. In this paper, we settle this conjecture completely by proving the following stronger statement; if the minimum degree sum of two nonadjacent vertices is at least 4r + 6s−1, then G contains a collection of r + s vertex-disjoint cycles such that s of them are chorded cycles.     

Dominating Sets and Eigenvalues of Graphs

The paper is concerned with dominating sets which arise naturallyfrom a star partition of a finite graph. Techniques from linearalgebra are used to construct certain graphs in which a dominatingset is minimal.     

Minimum Degree and Dominating Paths

A dominating path in a graph is a path P such that every vertex outside P has a neighbor on P. A result of Broersma from 1988 implies that if G is an n‐vertex k‐connected graph and , then G contains a dominating path. We prove the following results. The lengths of dominating paths include all values from the shortest up to at least . For , where a is a constant greater than 1/3, the minimum length of a dominating path is at most logarithmic in n when n is sufficiently large (the base of the logarithm depends on a). The preceding results are sharp. For constant s and , an s‐vertex dominating path is guaranteed by when n is sufficiently large, but (where ) does not even guarantee a dominating set of size s. We also obtain minimum‐degree conditions for the existence of a spanning tree obtained from a dominating path by giving the same number of leaf neighbors to each vertex.     

Induced Cycles in Graphs

The maximum number vertices of a graph G inducing a 2-regular subgraph of G is denoted by \(c_\mathrm{ind}(G)\). We prove that if G is an r-regular graph of order n, then \(c_\mathrm{ind}(G) \ge \frac{n}{2(r-1)} + \frac{1}{(r-1)(r-2)}\) and we prove that if G is a cubic, claw-free graph on order n, then \(c_\mathrm{ind}(G) > \frac{13}{20}n\) and this bound is asymptotically best possible.     

Decomposing Graphs of High Minimum Degree into 4‐Cycles

If a graph G decomposes into edge‐disjoint 4‐cycles, then each vertex of G has even degree and 4 divides the number of edges in G. It is shown that these obvious necessary conditions are also sufficient when G is any simple graph having minimum degree at least , where n is the number of vertices in G. This improves the bound given by Gustavsson (PhD Thesis, University of Stockholm, 1991), who showed (as part of a more general result) sufficiency for simple graphs with minimum degree at least . On the other hand, it is known that for arbitrarily large values of n there exist simple graphs satisfying the obvious necessary conditions, having n vertices and minimum degree , but having no decomposition into edge‐disjoint 4‐cycles. We also show that if G is a bipartite simple graph with n vertices in each part, then the obvious necessary conditions for G to decompose into 4‐cycles are sufficient when G has minimum degree at least .