共查询到20条相似文献,搜索用时 46 毫秒
1.
Let G=(V1,V2;E) be a bipartite graph with |V1|=|V2|=3k, where k>0. In this paper it is proved that if d(x)+d(y)≥4k−1 for every pair of nonadjacent vertices x∈V1, y∈V2, then G contains k−1 independent cycles of order 6 and a path of order 6 such that all of them are independent. Furthermore, if d(x)+d(y)≥4k for every pair of nonadjacent vertices x∈V1, y∈V2 and k>2, then G contains k−2 independent cycles of order 6 and a cycle of order 12 such that all of them are independent. 相似文献
2.
This paper considers the solution of the problem: inff[y, x(y)] s.t.y
[y, x(y)] E
k
, wherex(y) solves: minF(x, y) s.t.x R(x, y) E
n
. In order to obtain local solutions, a first-order algorithm, which uses {dx(y)/dy} for solving a special case of the implicitly definedy-problem, is given. The derivative is obtained from {dx(y, r)/dy}, wherer is a penalty function parameter and {x(y, r)} are approximations to the solution of thex-problem given by a sequential minimization algorithm. Conditions are stated under whichx(y, r) and {dx(y, r)/dy} exist. The computation of {dx(y, r)/dy} requires the availability of
y
F(x, y) and the partial derivatives of the other functions defining the setR(x, y) with respect to the parametersy.Research sponsored by National Science Foundation Grant ECS-8709795 and Office of Naval Research Contract N00014-89-J-1537. We thank the referees for constructive comments on an earlier version of this paper. 相似文献
3.
Given a graphG onn vertices and a total ordering ≺ ofV(G), the transitive orientation ofG associated with ≺, denotedP(G; ≺), is the partial order onV(G) defined by settingx<y inP(G; ≺) if there is a pathx=x
1
x
2…x
r=y inG such thatx
1 ≺x
j for 1≦i<j≦r. We investigate graphsG such that every transitive orientation ofG contains
2
n
−o(n
2) relations. We prove that almost everyG
n,p satisfies this requirement if
, but almost noG
n,p satisfies the condition if (pn log log logn)/(logn log logn) is bounded. We also show that every graphG withn vertices and at mostcn logn edges has some transitive orientation with fewer than
2
n
−δ(c)n
2 relations.
Partially supported by MCS Grant 8104854. 相似文献
4.
Reinhard Wolf 《Arkiv f?r Matematik》1997,35(2):387-400
One of our main results is the following: LetX be a compact connected subset of the Euclidean spaceR
n
andr(X, d
2) the rendezvous number ofX, whered
2 denotes the Euclidean distance inR
n
. (The rendezvous numberr(X, d
2) is the unique positive real number with the property that for each positive integern and for all (not necessarily distinct)x
1,x
2,...,x
n
inX, there exists somex inX such that
.) Then there exists some regular Borel probability measure μ0 onX such that the value of ∫
X
d
2(x, y)dμ0 (y) is independent of the choicex inX, if and only ifr(X, d
2) = supμ ∫
X
∫
X
d
2(x, y)dμ(x)dμ(y), where the supremum is taken over all regular Borel probability measures μ onX. 相似文献
5.
ForX a set the expression Prt(X) denotes the composition monoid of all functionsf X ×X. Fork a positive integer the letterk denotes also the set of all nonnegative integers less thank. Whenk > 1 the expression rk denotes the connected injective element {<i, i + 1>i k – 1} in Prt (k). We show for every word w=w(x,y) in a two-letter alphabet that if the equation w(x, y)=rk has a solution =y) 2Prt(k) then ¯w(x,y)=rk also has a solution in2Prt(k), where ¯w is the word obtained by spelling the wordw backwards. It is a consequence of this theorem that if for every finite setX and for everyf Prt(X) the equation w(x,y)=f has a solution in2Prt(X) then for every suchX andf the equation ¯w(x, y)=f has a solution in2Prt(X).Presented by J. Mycielski. 相似文献
6.
Let G be a graph and S ⊂ V(G). We denote by α(S) the maximum number of pairwise nonadjacent vertices in S. For x, y ∈ V(G), the local connectivity κ(x, y) is defined to be the maximum number of internally-disjoint paths connecting x and y in G. We define . In this paper, we show that if κ(S) ≥ 3 and for every independent set {x
1, x
2, x
3, x
4} ⊂ S, then G contains a cycle passing through S. This degree condition is sharp and this gives a new degree sum condition for a 3-connected graph to be hamiltonian. 相似文献
7.
For a setS of points in the plane, letd
1>d
2>... denote the different distances determined byS. Consider the graphG(S, k) whose vertices are the elements ofS, and two are joined by an edge iff their distance is at leastd
k
. It is proved that the chromatic number ofG(S, k) is at most 7 if |S|constk
2. IfS consists of the vertices of a convex polygon and |S|constk
2, then the chromatic number ofG(S, k) is at most 3. Both bounds are best possible. IfS consists of the vertices of a convex polygon thenG(S, k) has a vertex of degree at most 3k – 1. This implies that in this case the chromatic number ofG(S, k) is at most 3k. The best bound here is probably 2k+1, which is tight for the regular (2k+1)-gon. 相似文献
8.
Let X=(x1, ..., xn) and Y=(y1, ..., ym) be independent samples from populations Gx and Gy, x(1) ,... x(n) be ordered statistics constructed from the sample X. A model of trials associated with the occurrence of dependent events Ak={yk (x(i)}, x(j), i < j, k=1, 2, ..., m, where x(i), x(j) are order statistics, is considered. This model is a generalization of the Bernoulli model. Distribution of frequencies of occurrences of events Ak and the limit theorems which describe asymptotic properties of these frequencies are investigated.Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 42, No. 4, pp. 518–528, April, 1990. 相似文献
9.
Guangfu Zhao 《应用数学学报(英文版)》1987,3(2):111-121
A graphG is said to be embeddable into a graphH, if there is an isomorphism ofG into a subgraph ofH. It is shown in this paper that every unicycle or tree which is neither a path norK
1,3 embeds in itsn-th iterated line graph forn1 or 2, 3, and that every other connected graph that embeds in itsn-th iterated line graph may be constructed from such an embedded unicycle or tree in a natural way. A special kind of embedding of graph into itsn-th iterated line graph, called incidence embedding, is studied. Moreover, it is shown that for every positive integerk, there exists a graphG such that (G) = , where (G) is the leastn1 for whichG embeds inL
n(G). 相似文献
10.
It is proved that if a graphG has maximum degreed, then its vertices can be represented by distinct unit vectors inR
2d so that two vectors are orthogonal if and only if the corresponding vertices are adjacent. As a corollary it follows that if a graph has maximum degreed, then it is isomorphic to a unit distance graph inR
2d. 相似文献
11.
Manfred Peter 《Monatshefte für Mathematik》1996,121(4):335-352
Lattice points below Algebraic Curves. A generalization of the classical circle problem is treated. An asymptotic formula for the number of lattice points in a region whose boundary is an algebraic curve is obtained. This gives a mean value formula for the number of representations of the positive integers in the formn=g(x,y), whereg is a polynomial with coefficients 0 and leading terma
d0xd*a0dyd. The caseg(x,y)=p1(x)+p2(y) was considered inKuba andNowak [4], andKuba [5]. The discrete Hardy-Littlewood method is used along with Rouché's theorem. 相似文献
12.
The average distance μ(G) of a connected graph G of order n is the average of the distances between all pairs of vertices of G, i.e., μ(G) = ()−1 Σ{x,y}⊂V(G) dG(x, y), where V(G) denotes the vertex set of G and dG(x, y) is the distance between x and y. We prove that every connected graph of order n and minimum degree δ has a spanning tree T with average distance at most . We give improved bounds for K3‐free graphs, C4‐free graphs, and for graphs of given girth. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 1–13, 2000 相似文献
13.
Hong Wang 《Graphs and Combinatorics》1996,12(1):373-384
Letk be an integer withk 2. LetG = (A, B; E) be a 2-connected bipartite graph. Supposed(x) + d(y) k + 1 for every pair of non-adjacent verticesx andy. ThenG contains a cycle of length at leastmin(2a, 2k) wherea = min(|A|,|B|), unlessG is one of some known exceptions. We conjecture that if|A| = |B| andd(x) + d(y) k + 1 for every pair of non-adjacent verticesx andy withx A andy B, thenG contains a cycle of length at leastmin(2a, 2k). 相似文献
14.
In this paper, we show the equivalence of somequasi-random properties for sparse graphs, that is, graphsG with edge densityp=|E(G)|/(
2
n
)=o(1), whereo(1)→0 asn=|V(G)|→∞. Our main result (Theorem 16) is the following embedding result. For a graphJ, writeN
J(x) for the neighborhood of the vertexx inJ, and letδ(J) andΔ(J) be the minimum and the maximum degree inJ. LetH be atriangle-free graph and setd
H=max{δ(J):J⊆H}. Moreover, putD
H=min{2d
H,Δ(H)}. LetC>1 be a fixed constant and supposep=p(n)≫n
−1
D
H. We show that ifG is such that
Moreover, we discuss a setting under which an arbitrary graphH (not necessarily triangle-free) can be embedded inG. We also present an embedding result for directed graphs.
Research supported by a CNPq/NSF cooperative grant.
Partially supported by MCT/CNPq through ProNEx Programme (Proc. CNPq 664107/1997-4) and by CNPq (Proc. 300334/93-1 and 468516/2000-0).
Partially supported by NSF Grant 0071261.
Supported by NSF grant CCR-9820931. 相似文献
(i) | deg G (x)≤C pn for allx∈V(G), | ||
(ii) |
for all 2≤r≤D
H and for all distinct verticesx
1, ...,x
r ∈V(G), |
||
(iii) |
for all but at mosto(n
2) pairs {x
1,x
2} ⊆V(G), |
15.
James E. Williamson 《Periodica Mathematica Hungarica》1977,8(2):105-116
A graphG of orderp is said to bepanconnected if for each pairu, v of vertices ofG, there exists a,u, v-path of lengthl inG, for eachl such that dG(u, v)lp – 1, whered
G
(u, v) denotes the length of a shortestu, v-path inG. Three conditions are shown to be sufficient for a graphG of orderp to be panconnected: (1) the degree of each vertex ofG is at least (p+2)/2; (2) the sum of the degrees of each pair of nonadjacent vertices ofG is at least (3p–2)/2; (3) the graphG has at least
edges. It is also shown that each of these conditions is best possible. Additional results on panconnectedness are obtained including a characterization of those completen-partite graphs which are panconnected. 相似文献
16.
For x and y vertices of a connected graph G, let TG(x, y) denote the expected time before a random walk starting from x reaches y. We determine, for each n > 0, the n-vertex graph G and vertices x and y for which TG(x, y) is maximized. the extremal graph consists of a clique on ?(2n + 1)/3?) (or ?)(2n ? 2)/3?) vertices, including x, to which a path on the remaining vertices, ending in y, has been attached; the expected time TG(x, y) to reach y from x in this graph is approximately 4n3/27. 相似文献
17.
Ari Vesanen 《代数通讯》2013,41(4):1177-1195
ABSTRACT We introduce the notion of weak transitivity for torsion-free abelian groups. A torsion-free abelian group G is called weakly transitive if for any pair of elements x, y ∈ G and endomorphisms ?, ψ ∈ End(G) such that x? = y, yψ = x, there exists an automorphism of G mapping x onto y. It is shown that every suitable ring can be realized as the endomorphism ring of a weakly transitive torsion-free abelian group, and we characterize up to a number-theoretical property the separable weakly transitive torsion-free abelian groups. 相似文献
18.
Guizhen Liu 《应用数学学报(英文版)》1987,3(4):313-317
The connectivity and the circuit rank of a graphG are denoted byx(G) and, respectively. It is shown that ifH is the adjacent tree graph of a simple connected graphG, thenx(H)=2. 相似文献
19.
K. Retert 《Algebras and Representation Theory》2004,7(3):287-341
Noncommutative projective geometry studies noncommutative graded rings by replacing the variety by a suitable Grothendieck category. One way of studying the resulting category is to examine the full subcategories which behave like curves on a commutative variety. Smith and Zhang initiated such a study by considering the subcategory generated by a particular type of module they called a pure curve module in good position. This paper generalizes their construction by allowing more general modules. The resulting category is shown to be categorically equivalent to a quotient of the category of graded modules over a graded ring. In the course of defining the category equivalence, several dimensions, including projective, injective and Krull dimensions, are calculated. In particular, this extension allows examination of the category created from a line module over more general AS-regular rings than those considered by Smith and Zhang. For instance, suppose that C is a generic line module over R
d
, Stafford's Sklyanin-like algebra. Let C denote the category C generates. Then C is equivalent to the category of graded k[x, y]/(x
2 – y
2) modules under the Z × Z/2Z-grading where deg(x) = (–1, 0) and deg(y) = (–1,1). 相似文献
20.
Letk be an algebraically closed field of characteristic 0 and letf(x, y)k[t][x,y] be a polynomial in two variables with coefficients ink[t]. One is interested in solving the equationf(x,y)=0 with polynomialsx,yk[t]. Two solutions(x,y), (x, y) areproportional ifx/x andy/y are non-zero constants ink and a solution(x,y) isprimitive if the polynomialsx andy have no common root. The main result of this paper is that for a certain class of polynomialsf, which includes Thue equations with sufficiently lacunary exponents, the number of non-proportional, primitive solutions is bounded solely in terms of the number of monomials
appearing in the polynomialf(x,y). This verifies the analogue of a conjecture of Siegel for this class of polynomials. The proof is an application of theabc-theorem in function fields to certain determinantal varieties arising from the elimination of the coefficients of the polynomialf(x,y), together with an inductive argument on the numberr of monomials inf(x,y). 相似文献