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].     

Sufficient conditions for a graph to be edge-colorable with maximum degree colors

We study properties of graphs related to the existence of certain vertex and edge partitions. These properties give sufficient conditions for a graph to be Class 1 (i.e., edge-colorable with maximum degree colors). We apply these conditions for solving the classification problem for graphs with acyclic core (the subgraph induced by the maximum degree vertices), and for subclasses of join graphs and cobipartite graphs.     

Sufficient conditions for a graph to be Hamiltonian

Three sufficient conditions for a graph to be Hamiltonian are given. These theorems are in terms of subgraph structure and do not require the fairly high global line density which is basic to the Pósa-like sufficiency conditions. Line graphs of both Eulerian graphs and Hamiltonian graphs are also characterized.     

Complete graph immersions and minimum degree

An immersion of a graph H in another graph G is a one‐to‐one mapping and a collection of edge‐disjoint paths in G, one for each edge of H, such that the path corresponding to the edge has endpoints and . The immersion is strong if the paths are internally disjoint from . We prove that every simple graph of minimum degree at least contains a strong immersion of the complete graph . This improves on previously known bound of minimum degree at least 200t obtained by DeVos et al. Our result supports a conjecture of Lescure and Meyniel (also independently proposed by Abu‐Khzam and Langston), which is the analogue of famous Hadwiger’s conjecture for immersions and says that every graph without a ‐immersion is ‐colorable.     

Sufficient conditions for a control to be a strong minimum

The control literature either presents sufficient conditions for global optimality (for example, the Hamilton-Jacobi-Bellman theorem) or, if concerned with local optimality, restricts attention to comparison controls which are local in theL -sense. In this paper, use is made of an exact expression for the change in cost due to a change in control, a natural extension of a result due to Weierstrass, to obtain sufficient conditions for a control to be a strong minimum (in the sense that comparison controls are merely required to be close in theL ₁-sense).     

The minimum degree threshold for perfect graph packings

Let H be any graph. We determine up to an additive constant the minimum degree of a graph G which ensures that G has a perfect H-packing (also called an H-factor). More precisely, let δ(H,n) denote the smallest integer k such that every graph G whose order n is divisible by |H| and with δ(G)≥k contains a perfect H-packing. We show that

Sufficient conditions for a global minimum in a nonlinear programming problem

Translated from Issledovaniya po Prikladnoi Matematike, No. 1, pp. 103–108, 1973.     

Sufficient conditions for a minimum of the free-final-time optimal control problem

The sufficient conditions for a minimum of the free-final-time optimal control problem are the strengthened Legendre-Clebsch condition and the conjugate point condition. In this paper, a new approach for determining the location of the conjugate point is presented. The sweep method is used to solve the linear two-point boundary-value problem for the neighboring extremal path from a perturbed initial point to the final constraint manifold. The new approach is to solve for the final condition Lagrange multiplier perturbation and the final time perturbation simultaneously. Then, the resulting neighboring extremal control is used to write the second variation as a perfect square and obtain the conjugate point condition. Finally, two example problems are solved to illustrate the application of the sufficient conditions.     

图的彩虹连通数与最小度和

令G是一个阶为n且最小度为δ的连通图. 当δ很小而n很大时, 现有的依据于最小度参数的彩虹边连通数和彩虹点连通数的上界都很大, 它们是n的线性函数. 本文中, 我们用另一种参数,即k个独立点的最小度和σ_k来代替δ, 从而在很大程度上改进了彩虹边连通数和彩虹点连通数的上界. 本文证明了如果G有k个独立点, 那么rc(GG)≤3kn/(σk+k)+6k-3. 同时也证明了下面的结果, 如果σ_k≤7k或σ_k≥8k, 那么rvc(G)≤(4k+2k²)n/(σ_k+k)+5k; 如果7k<σ_k<8k, 那么rvc(G)≤(38k/9+2k²)n/(σ_k+k)+5k.文中也给出了例子说明我们的界比现有的界更好, 即我们的界为rc(G)≤9k-3和rvc(G)≤9k+2k²或rvc(G)≤83k/9+2k², 这意味着当δ很小而σ_k很大时, 我们的界是一个常数, 而现有的界却是n的线性函数.     

On graphs with equal edge connectivity and minimum degree

The note contains some conditions on a graph implying that the edge connectivity is equal to the minimum degree. One of these conditions is that if d₁?d₂???d_n is the degree sequence then ∑^l_l?1(d₁+d_n?1)>In?1 for $\text{1 ? l? min {}\text{n}\text{2?1}\text{, d}{}_{\mathrm{n}}\text{}}$.     

Maximum Zagreb index, minimum hyper-Wiener index and graph connectivity

In this work we show that among all n-vertex graphs with edge or vertex connectivity k, the graph G=K_k(K₁+K_n−k−1), the join of K_k, the complete graph on k vertices, with the disjoint union of K₁ and K_n−k−1, is the unique graph with maximum sum of squares of vertex degrees. This graph is also the unique n-vertex graph with edge or vertex connectivity k whose hyper-Wiener index is minimum.     

Sufficient conditions for a strong relative minimum in an optimal control problem

In this paper, on the basis of Young's method (Ref. 1), sufficient conditions for a strong relative minimum in an optimal control problem are given. Young's method generalizes geodesic coverings and the simplest Hilbert integral from the standard variational calculus. This paper carries Young's method over to nonparametric problems.     

On a classical theorem on the diameter and minimum degree of a graph

In this work, we obtain good upper bounds for the diameter of any graph in terms of its minimum degree and its order, improving a classical theorem due to Erd¨os, Pach, Pollack and Tuza.We use these bounds in order to study hyperbolic graphs(in the Gromov sense). To compute the hyperbolicity constant is an almost intractable problem, thus it is natural to try to bound it in terms of some parameters of the graph. Let H(n, δ_0) be the set of graphs G with n vertices and minimum degree δ_0, and J(n, Δ) be the set of graphs G with n vertices and maximum degree Δ. We study the four following extremal problems on graphs: a(n, δ_0) = min{δ(G) | G ∈ H(n, δ_0)}, b(n, δ_0) = max{δ(G) |G ∈ H(n, δ_0)}, α(n, Δ) = min{δ(G) | G ∈ J(n, Δ)} and β(n, Δ) = max{δ(G) | G ∈ J(n, Δ)}. In particular, we obtain bounds for b(n, δ_0) and we compute the precise value of a(n, δ_0), α(n, Δ) andβ(n, Δ) for all values of n, δ_0 and Δ, respectively.     

Sufficient conditions for the existence of a graph with a given variety of balls

It is proved that for each positive integer d and each collection of integers $\bar \tau $ = (τ ₀, τ ₁ …, τ _d ) such that τ ₀ ? τ ₁ ? … ? τ _d = 1 and τ _d?1 ? d ² + 1, there exists a graph of diameter d whose variety vector of the balls is equal to $\bar \tau $ ; if d ? 3 then there is no graph of diameter d whose variety vector of balls (τ ₀, τ ₁, …, τ _d ) satisfies the condition τ ₀ = τ ₁ = … = τ _d?1 ? 2d ? 1.     

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.     

Sufficient conditions for stochastic equality of two distributions under some partial orders

We establish some conditions for stochastic equality of two nonnegative random variables which are ordered with respect to variability ordering or with respect to mean residual life ordering or with respect to second order stochastic ordering.     

Degree sequence conditions for equal edge‐connectivity and minimum degree,depending on the clique number

Using the well‐known Theorem of Turán, we present in this paper degree sequence conditions for the equality of edge‐connectivity and minimum degree, depending on the clique number of a graph. Different examples will show that these conditions are best possible and independent of all the known results in this area. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 234–245, 2003     

The connectivity and minimum degree of circuit graphs of matroids

Let G be the circuit graph of any connected matroid M with minimum degree 5（G）. It is proved that its connectivity κ（G） ≥2｜E（M） - B（M）｜ - 2. Therefore 5（G） ≥ 2｜E（M） - B（M）｜ - 2 and this bound is the best possible in some sense.     

An upper bound for the restrained domination number of a graph with minimum degree at least two in terms of order and minimum degree

Let G=(V,E) be a graph. A set S⊆V is a restrained dominating set if every vertex in V−S is adjacent to a vertex in S and to a vertex in V−S. The restrained domination number of G, denoted γ_r(G), is the smallest cardinality of a restrained dominating set of G. We will show that if G is a connected graph of order n and minimum degree δ and not isomorphic to one of nine exceptional graphs, then .