共查询到20条相似文献,搜索用时 31 毫秒
1.
Anders Yeo 《Journal of Graph Theory》1999,32(2):123-136
The local irregularity of a digraph D is defined as il(D) = max {|d+ (x) − d− (x)| : x ϵ V(D)}. Let T be a tournament, let Γ = {V1, V2, …, Vc} be a partition of V(T) such that |V1| ≥ |V2| ≥ … ≥ |Vc|, and let D be the multipartite tournament obtained by deleting all the arcs with both end points in the same set in Γ. We prove that, if |V(T)| ≥ max{2il(T) + 2|V1| + 2|V2| − 2, il(T) + 3|V1| − 1}, then D is Hamiltonian. Furthermore, if T is regular (i.e., il(T) = 0), then we state slightly better lower bounds for |V(T)| such that we still can guarantee that D is Hamiltonian. Finally, we show that our results are best possible. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 123–136, 1999 相似文献
2.
3.
Xin Min Hou 《数学学报(英文版)》2012,28(11):2161-2168
A graph G satisfies the Ore-condition if d(x) + d(y) ≥ | V (G) | for any xy ■ E(G). Luo et al. [European J. Combin., 2008] characterized the simple Z3-connected graphs satisfying the Ore-condition. In this paper, we characterize the simple Z3-connected graphs G satisfying d(x) + d(y) ≥ | V (G) |-1 for any xy ■ E(G), which improves the results of Luo et al. 相似文献
4.
B. A. Khudaikuliev 《Mathematical Notes》2012,92(5-6):820-829
This paper deals with the behavior of the nonnegative solutions of the problem $$- \Delta u = V(x)u, \left. u \right|\partial \Omega = \varphi (x)$$ in a conical domain Ω ? ? n , n ≥ 3, where 0 ≤ V (x) ∈ L1(Ω), 0 ≤ ?(x) ∈ L1(?Ω) and ?(x) is continuous on the boundary ?Ω. It is proved that there exists a constant C *(n) = (n ? 2)2/4 such that if V 0(x) = (c + λ 1)|x|?2, then, for 0 ≤ c ≤ C *(n) and V(x) ≤ V 0(x) in the domain Ω, this problem has a nonnegative solution for any nonnegative boundary function ?(x) ∈ L 1(?Ω); for c > C *(n) and V(x) ≥ V 0(x) in Ω, this problem has no nonnegative solutions if ?(x) > 0. 相似文献
5.
Bela Bajnok 《Graphs and Combinatorics》1991,7(3):219-233
A finite subsetX of thed-dimensional unit sphereS d-1 is called a sphericalt-design, if and only if $$\frac{1}{{\left| {S^{d - 1} } \right|}}\int_{S^{d - 1} } {f(x)d\omega (x)} = \frac{1}{{\left| x \right|}}\sum\limits_{x \in X} {f(x)} $$ holds for all polynomialsf(x) =f(x 1,x 2,...,x d ) of degree at mostt. In 1984 Seymour and Zaslavsky proved the existence of sphericalt-designs for anyt andd, but for sufficiently large |X|. Since spherical designs can be used for numerical integration, it is of interest to give explicit constructions. Mimura gave a construction fort = 2,d ∈ ? and |X| ≥n 2 for somen 2 ∈ ? (n 2 is sharp). Here we will give an explicit construction fort = 4 and 5,d ∈ ? and |X| ≥n 4 for somen 4 ∈ ?. 相似文献
6.
Pierre Fraisse 《Journal of Graph Theory》1986,10(4):553-557
Let G = (V, E) be a digraph of order n, satisfying Woodall's condition ? x, y ∈ V, if (x, y) ? E, then d+(x) + d?(y) ≥ n. Let S be a subset of V of cardinality s. Then there exists a circuit including S and of length at most Min(n, 2s). In the case of oriented graphs we obtain the same result under the weaker condition d+(x) + d?(y) ≥ n – 2 (which implies hamiltonism). 相似文献
7.
In this paper, we obtain the following result: Let k, n
1 and n
2 be three positive integers, and let G = (V
1,V
2;E) be a bipartite graph with |V1| = n
1 and |V
2| = n
2 such that n
1 ⩾ 2k + 1, n
2 ⩾ 2k + 1 and |n
1 − n
2| ⩽ 1. If d(x) + d(y) ⩾ 2k + 2 for every x ∈ V
1 and y ∈ V
2 with xy
$
\notin
$
\notin
E(G), then G contains k independent cycles. This result is a response to Enomoto’s problems on independent cycles in a bipartite graph. 相似文献
8.
How Close to Regular Must a Semicomplete Multipartite Digraph Be to Secure Hamiltonicity? 总被引:1,自引:0,他引:1
Anders Yeo 《Graphs and Combinatorics》1999,15(4):481-493
Let D be a semicomplete multipartite digraph, with partite sets V
1, V
2,…, V
c, such that |V
1|≤|V
2|≤…≤|V
c|. Define f(D)=|V(D)|−3|V
c|+1 and . We define the irregularity i(D) of D to be max|d
+(x)−d
−(y)| over all vertices x and y of D (possibly x=y). We define the local irregularity i
l(D) of D to be max|d
+(x)−d
−(x)| over all vertices x of D and we define the global irregularity of D to be i
g(D)=max{d
+(x),d
−(x) : x∈V(D)}−min{d
+(y),d
−(y) : y∈V(D)}. In this paper we show that if i
g(D)≤g(D) or if i
l(D)≤min{f(D), g(D)} then D is Hamiltonian. We furthermore show how this implies a theorem which generalizes two results by Volkmann and solves a stated
problem and a conjecture from [6]. Our result also gives support to the conjecture from [6] that all diregular c-partite tournaments (c≥4) are pancyclic, and it is used in [9], which proves this conjecture for all c≥5. Finally we show that our result in some sense is best possible, by giving an infinite class of non-Hamiltonian semicomplete
multipartite digraphs, D, with i
g(D)=i(D)=i
l(D)=g(D)+?≤f(D)+1.
Revised: September 17, 1998 相似文献
9.
Let R be a prime ring of char R≠2, d a non-zero derivation of R and ρ a non-zero right ideal of R such that [[d(x),d(y)]n [y,x]m] = 0 for all x,y ∈ ρ or [[d(x),d(y)]n d[y,x]m] = 0 for all x,y ∈ ρ, n, m ≥ 0 are fixed integers. If [ρ,ρ]ρ ≠ 0, then d(ρ)ρ = 0. 相似文献
10.
Hong Wang 《Journal of Graph Theory》1997,26(2):105-109
We propose a conjecture: for each integer k ≥ 2, there exists N(k) such that if G is a graph of order n ≥ N(k) and d(x) + d(y) ≥ n + 2k - 2 for each pair of non-adjacent vertices x and y of G, then for any k independent edges e1, …, ek of G, there exist k vertex-disjoint cycles C1, …, Ck in G such that ei ∈ E(Ci) for all i ∈ {1, …, k} and V(C1 ∪ ···∪ Ck) = V(G). If this conjecture is true, the condition on the degrees of G is sharp. We prove this conjecture for the case k = 2 in the paper. © 1997 John Wiley & Sons, Inc. J Graph Theory 26: 105–109, 1997 相似文献
11.
Hong Wang 《Journal of Graph Theory》1999,31(2):101-106
In this article, we consider the following problem: Given a bipartite graph G and a positive integer k, when does G have a 2‐factor with exactly k components? We will prove that if G = (V1, V2, E) is a bipartite graph with |V1| = |V2| = n ≥ 2k + 1 and δ (G) ≥ ⌈n/2⌉ + 1, then G contains a 2‐factor with exactly k components. We conjecture that if G = (V1, V2; E) is a bipartite graph such that |V1| = |V2| = n ≥ 2 and δ (G) ≥ ⌈n/2⌉ + 1, then, for any bipartite graph H = (U1, U2; F) with |U1| ≤ n, |U2| ≤ n and Δ (H) ≤ 2, G contains a subgraph isomorphic to H. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 101–106, 1999 相似文献
12.
13.
Let G be a connected simple graph, let X?V (G) and let f be a mapping from X to the set of integers. When X is an independent set, Frank and Gyárfás, and independently, Kaneko and Yoshimoto gave a necessary and sufficient condition for the existence of spanning tree T in G such that d T (x) for all x ∈ X, where d T (x) is the degree of x and T. In this paper, we extend this result to the case where the subgraph induced by X has no induced path of order four, and prove that there exists a spanning tree T in G such that d T (x) ≥ f(x) for all x ∈ X if and only if for any nonempty subset S ? X, |N G (S) ? S| ? f(S) + 2|S| ? ω G (S) ≥, where ω G (S) is the number of components of the subgraph induced by S. 相似文献
14.
G. A. Dzyubenko 《Ukrainian Mathematical Journal》1996,48(3):367-376
We prove that if a functionf ∈C (1) (I),I: = [?1, 1], changes its signs times (s ∈ ?) within the intervalI, then, for everyn > C, whereC is a constant which depends only on the set of points at which the function changes its sign, andk ∈ ?, there exists an algebraic polynomialP n =P n (x) of degree ≤n which locally inherits the sign off(x) and satisfies the inequality $$\left| {f\left( x \right) - P_n \left( x \right)} \right| \leqslant c\left( {s,k} \right)\left( {\frac{1}{{n^2 }} + \frac{{\sqrt {1 - x^2 } }}{n}} \right)\omega _k \left( {f'; \frac{1}{{n^2 }} + \frac{{\sqrt {1 - x^2 } }}{n}} \right), x \in I$$ , where ω k (f′;t) is thekth modulus of continuity of the functionf’. It is also shown that iff ∈C (I) andf(x) ≥ 0,x ∈I then, for anyn ≥k ? 1, there exists a polynomialP n =P n (x) of degree ≤n such thatP n (x) ≥ 0,x ∈I, and |f(x) ?P n (x)| ≤c(k)ω k (f;n ?2 +n ?1 √1 ?x 2),x ∈I. 相似文献
15.
In 1990 G. T. Chen proved that if G is a 2-connected graph of order n and 2|N(x) ∪ N(y)| + d(x) + d(y) ≥ 2n − 1 for each pair of nonadjacent vertices x, y ∈ V (G), then G is Hamiltonian. In this paper we prove that if G is a 2-connected graph of order n and 2|N(x) ∪ N(y)| + d(x)+d(y) ≥ 2n−1 for each pair of nonadjacent vertices x, y ∈ V (G) such that d(x, y) = 2, then G is Hamiltonian. 相似文献
16.
The assignment problem may be stated as follows: Given finite sets of points S and T, with|S| ? |T|, and given a “metric” which assigns a distance d(x, y) to each pair (x, y) such that x ∈ T and y ∈ S find a 1?1 function Q: T→ S which minimizes Σx∈Td(x, Q(x)) We consider the two special cases in which the points lie (1) on a line segment and (2) on a circle, and the metric is the distance along the line segment or circle, respectively. In each case, we show that the optimal assignment Q can be computed in a number of steps (additions and comparisons) proportional to the number of points. The problem arose in connection with the efficient rearrangement of desks located in offices along a corridor which encircles one floor of a building. 相似文献
17.
G. A. Kalyabin 《Proceedings of the Steklov Institute of Mathematics》2014,284(1):161-167
Explicit upper and lower estimates are given for the norms of the operators of embedding of , n ∈ ?, in L q (dµ), 0 < q < ∞. Conditions on the measure µ are obtained under which the ratio of the above estimates tends to 1 as n → ∞, and asymptotic formulas are presented for these norms in regular cases. As a corollary, an asymptotic formula (as n → ∞) is established for the minimum eigenvalues λ1, n, β , β > 0, of the boundary value problems (?d 2/dx 2) n u(x) = λ|x| β?1, x ∈ (?1, 1), u (k)(±1) = 0, k ∈ {0, 1, ..., n ? 1}. 相似文献
18.
Rossitza I. Semerdjieva 《Mathematische Nachrichten》2002,237(1):89-104
Let k(y) > 0, 𝓁(y) > 0 for y > 0, k(0) = 𝓁(0) = 0 and limy → 0k(y)/𝓁(y) exists; then the equation L(u) ≔ k(y)uxx – ∂y(𝓁(y)uy) + a(x, y)ux = f(x, y, u) is strictly hyperbolic for y > 0 and its order degenerates on the line y = 0. Consider the boundary value problem Lu = f(x, y, u) in G, u|AC = 0, where G is a simply connected domain in ℝ2 with piecewise smooth boundary ∂G = AB∪AC∪BC; AB = {(x, 0) : 0 ≤ x ≤ 1}, AC : x = F(y) = ∫y0(k(t)/𝓁(t))1/2dt and BC : x = 1 – F(y) are characteristic curves. Existence of generalized solution is obtained by a finite element method, provided f(x, y, u) satisfies Carathéodory condition and |f(x, y, u)| ≤ Q(x, y) + b|u| with Q ∈ L2(G), b = const > 0. It is shown also that each generalized solution is a strong solution, and that fact is used to prove uniqueness under the additional assumption |f(x, y, u1) – f(x, y, u2| ≤ C|u1 – u2|, where C = const > 0. 相似文献
19.
Ioan Tomescu 《Discrete Applied Mathematics》2010,158(15):1714-1717
The concept of degree distance of a connected graph G is a variation of the well-known Wiener index, in which the degrees of vertices are also involved. It is defined by D′(G)=∑x∈V(G)d(x)∑y∈V(G)d(x,y), where d(x) and d(x,y) are the degree of x and the distance between x and y, respectively. In this paper it is proved that connected graphs of order n≥4 having the smallest degree distances are K1,n−1,BS(n−3,1) and K1,n−1+e (in this order), where BS(n−3,1) denotes the bistar consisting of vertex disjoint stars K1,n−3 and K1,1 with central vertices joined by an edge. 相似文献
20.
《Comptes Rendus de l'Academie des Sciences Series IIA Earth and Planetary Science》1999,328(4):291-296
The purpose of this paper is to prove the existence of a solution for a nonlinear parabolic equation in the form ut - div(a(t, x, u, Du)) = H(t, x, u, Du) - div(g(t, x)) in QT =]0,T[×Ω, Ω ⊂ RN, with an initial condition u(0) = u0, where u0 is not bounded, |H(t,x, u, ξ)⩽ β|ξ|p + f(t,x) + βeλ1|u|f, |g|p/(p-1) ∈ Lr(QT) for some r = r{N) ⩾ 1, and - div(a(t,x,u, Du)) is the usual Leray-Lions operator. 相似文献