共查询到20条相似文献,搜索用时 93 毫秒
1.
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. 相似文献
2.
P. Erdös 《Israel Journal of Mathematics》1964,2(3):183-190
Anr-graph is a graph whose basic elements are its vertices and r-tuples. It is proved that to everyl andr there is anε(l, r) so that forn>n
0 everyr-graph ofn vertices andn
r−ε(l, r) r-tuples containsr. l verticesx
(j), 1≦j≦r, 1≦i≦l, so that all ther-tuples
occur in ther-graph. 相似文献
3.
H. Brézis 《Israel Journal of Mathematics》1971,9(4):513-534
Let φ be a convex l.s.c. function fromH (Hilbert) into ] - ∞, ∞ ] andD(φ)={u ∈H; φ(u)<+∞}. It is proved that for everyu
0 ∈D(φ) the equation − (du/dt)(t ∈ ∂φ(u(t)),u(0)=u
0 has a solution satisfying ÷(du(t)/dt)÷ ≦(c
1/t)+c
2. The behavior ofu(t) in the neighborhood oft=0 andt=+∞ as well as the inhomogeneous equation (du(t)/dt)+∂φ(u(t)) ∈f(t) are then studied. Solutions of some nonlinear boundary value problems are given as applications.
相似文献
4.
The Wiener index of a graph G is defined as W(G)=∑
u,v
d
G
(u,v), where d
G
(u,v) is the distance between u and v in G and the sum goes over all the pairs of vertices. In this paper, we first present the 6 graphs with the first to the sixth
smallest Wiener index among all graphs with n vertices and k cut edges and containing a complete subgraph of order n−k; and then we construct a graph with its Wiener index no less than some integer among all graphs with n vertices and k cut edges. 相似文献
5.
It is proved that if the Banach-Mazur distance between ann-dimensional Minkowski spaceB andl
2
n
satisfiesd (B
1
l
2
n
) ≧c √n (for some constantc>0 and for bign) thenB contains anA(c)-isomorphic copy ofl
1
k
(fork ∼ log log logn). In the special cased (B
1
l
2
n
) = √n,B contains an isometric copy ofl
1
k
fork ∼ logn. 相似文献
6.
Let G
m,n be the class of strategic games with n players, where each player has m≥2 pure strategies. We are interested in the structure of the set of correlated equilibria of games in G
m,n when n→∞. As the number of equilibrium constraints grows slower than the number of pure strategy profiles, it might be conjectured
that the set of correlated equilibria becomes large. In this paper, we show that (1) the average relative measure of the set
of correlated equilibria is smaller than 2−n; and (2) for each 1<c<m, the solution set contains c
n correlated equilibria having disjoint supports with a probability going to 1 as n grows large. The proof of the second result hinges on the following inequality: Let c
1, …, c
l be independent and symmetric random vectors in R
k, l≥k. Then the probability that the convex hull of c
1, …, c
l intersects R
k
+ is greater than or equal to .
Received: December 1998/Final version: March 2000 相似文献
7.
The Erdős-Sós conjecture says that a graph G on n vertices and number of edges e(G) > n(k− 1)/2 contains all trees of size k. In this paper we prove a sufficient condition for a graph to contain every tree of size k formulated in terms of the minimum edge degree ζ(G) of a graph G defined as ζ(G) = min{d(u) + d(v) − 2: uv ∈ E(G)}. More precisely, we show that a connected graph G with maximum degree Δ(G) ≥ k and minimum edge degree ζ(G) ≥ 2k − 4 contains every tree of k edges if d
G
(x) + d
G
(y) ≥ 2k − 4 for all pairs x, y of nonadjacent neighbors of a vertex u of d
G
(u) ≥ k. 相似文献
8.
Letf(s, t; k) be the largest value ofm such that it is possible tok-color the edges of the complete graphK
m
so that everyK
s
⊆K
m
has exactlyt colors occuring on its edges. The main object of this paper is to describe the behavior of the functionf(s,t;k), usually thinking ofs andt fixed, and lettingk become large.
Dedicated to Paul Erdős on his seventieth birthday 相似文献
9.
A k-edge-weighting w of a graph G is an assignment of an integer weight, w(e) ∈ {1,…,k}, to each edge e. An edge-weighting naturally induces a vertex coloring c by defining c(u) = Σ
e∋u
w(e) for every u ∈ V (G). A k-edge-weighting of a graph G is vertex-coloring if the induced coloring c is proper, i.e., c(u) ≠ c(v) for any edge uv ∈ E(G). When k ≡ 2 (mod 4) and k ⩾ 6, we prove that if G is k-colorable and 2-connected, δ(G) ⩾ k − 1, then G admits a vertex-coloring k-edge-weighting. We also obtain several sufficient conditions for graphs to be vertex-coloring k-edge-weighting.
相似文献
10.
Peter Frankl 《Combinatorica》1983,3(2):193-199
Letn, k, t be integers,n>k>t≧0, and letm(n, k, t) denote the maximum number of sets, in a family ofk-subsets of ann-set, no two of which intersect in exactlyt elements. The problem of determiningm(n, k, t) was raised by Erdős in 1975. In the present paper we prove that ifk≦2t+1 andk−t is a prime, thenm(n, k, t)≦(
t
n
)(
k
2k-t-1
)/(
t
2k-t-1
). Moreover, equality holds if and only if an (n, 2k−t−1,t)-Steiner system exists. The proof uses a linear algebraic approach. 相似文献
11.
Hiroshi Nagamochi Toshihide Ibaraki 《Journal of Algorithms in Cognition, Informatics and Logic》1999,30(2):253
For a given undirected graphG = (V, E, cG) with edges weighted by nonnegative realscG:E → R + , let ΛG(k) stand for the minimum amount of weights which needs to be added to makeG k-edge-connected, and letG*(k) be the resulting graph obtained fromG. This paper first shows that function ΛGover the entire rangek [0, +∞] can be computed inO(nm + n2 log n) time, and then shows that allG*(k) in the entire range can be obtained fromO(n log n) weighted cycles, and such cycles can be computed inO(nm + n2 log n) time, wherenandmare the numbers of vertices and edges, respectively. 相似文献
12.
Hong Wang 《Graphs and Combinatorics》2001,17(1):177-183
Let G=(V
1,V
2;E) be a bipartite graph with 2k≤m=|V
1|≤|V
2|=n, where k is a positive integer. We show that if the number of edges of G is at least (2k−1)(n−1)+m, then G contains k vertex-disjoint cycles, unless e(G)=(2k−1)(n−1)+m and G belongs to a known class of graphs.
Received: December 9, 1998 Final version received: June 2, 1999 相似文献
13.
For an ordered k-decomposition ? = {G
1, G
2,…,G
k
} of a connected graph G and an edge e of G, the ?-representation of e is the k-tuple r(e|?) = (d(e, G
1), d(e, G
2),…,d(e, G
k
)), where d(e, G
i
) is the distance from e to G
i
. A decomposition ? is resolving if every two distinct edges of G have distinct representations. The minimum k for which G has a resolving k-decomposition is its decomposition dimension dec(G). It is shown that for every two positive integers k and n≥ 2, there exists a tree T of order n with dec(T) = k. It is also shown that dec(G) ≤n for every graph G of order n≥ 3 and that dec(K
n
) ≤⌊(2n + 5)/3⌋ for n≥ 3.
Received: June 17, 1998 Final version received: August 10, 1999 相似文献
14.
A. J. W. Hilton 《Combinatorica》1982,2(1):37-51
A variety of results on edge-colourings are proved, the main one being the following: ifG is a graph without loops or multiple edges and with maximum degree Δ=Δ(G), and if ν is a given integer 1≦ν≦Δ(G), thenG can be given a proper edge-colouring with the coloursc
1, ...,c
Δ+1 with the additional property that any edge colouredc
μ with μ≧ν is on a vertex which has on it edges coloured with at least ν − 1 ofc
1, ...,c
v
. 相似文献
15.
Ralph J. Faudree 《Journal of Graph Theory》1992,16(4):327-334
Let t(n, k) denote the Turán number—the maximum number of edges in a graph on n vertices that does not contain a complete graph Kk+1. It is shown that if G is a graph on n vertices with n ≥ k2(k – 1)/4 and m < t(n, k) edges, then G contains a complete subgraph Kk such that the sum of the degrees of the vertices is at least 2km/n. This result is sharp in an asymptotic sense in that the sum of the degrees of the vertices of Kk is not in general larger, and if the number of edges in G is at most t(n, k) – ? (for an appropriate ?), then the conclusion is not in general true. © 1992 John Wiley & Sons, Inc. 相似文献
16.
LetM=(W, d) be a metric space. LetL
1 denote theL
1 metric. AnL
1-embedding ofM into Cartesiank-space ℝ
k
is a distance-preserving map from (W, d) into (ℝ
k
,L
1). Letc(k) be the smallest integer such that for every metric spaceM, M isL
1-embeddable inR
k iff everyc(k)-sized subspace ofM isL
1-embeddable inR
k. A special case of a theorem of Menger (see p. 94 of [5]) says thatc(1) exists and equals 4. We show thatc(2) exists and satisfies 6≦c(2)≦11. Whether or notc(k) exists for anyk≧3 is an open question.
The research of S. M. Malitz was partially supported by NSF Grant CCR-8909953. 相似文献
17.
A scheme is proposed for the feedback control of distributed-parameter systems with unknown boundary and volume disturbances and observation errors. The scheme consists of employing a nonlinear filter in the control loop such that the controller uses the optimal estimates of the state of the system. A theoretical comparison of feedback proportional control of a styrene polymerization reactor with and without filtering is presented. It is indicated how an approximate filter can be constructed, greatly reducing the amount of computing required.Notation
a(t)
l-vector noisy dynamic input to system
-
A(t, a)
l-vector function
-
A
frequency factor for first-order rate law (5.68×106 sec–1)
-
b
distance to the centerline between two coil banks in the reactor (4.7 cm)
-
B
k-vector function defining the control action
-
c(, )
concentration of styrene monomer, molel
–1
-
C
p
heat capacity (0.43 cal · g–1 · K–1)
-
C
ij
constants in approximate filter, Eqs. (49)–(52)
-
E
activation energy (20330 cal · mole–1)
-
expectation operator
-
f(t,...)
n-vector function
-
g
0,g
1(t,...)
n-vector functions
-
h(t, u)
m-vector function relating observations to states
-
H(t)
function defined in Eq. (36)
-
k
dimensionality of control vectorv(x, t)
-
k
i
constants in approximate filter, Eqs. (49)–(52)
-
K
dimensionless proportional gain
-
l
dimensionality of dynamic inputa(t)
-
m
dimensionality of observation vectory(t)
-
n
dimensionality of state vectoru(x, t)
-
P
(vv)(x, s, t)
n×n matrix governed by Eq. (9)
-
P
(va)(x, t)
n×l matrix governed by Eq. (10)
-
P
(aa)(t)
l×l matrix governed by Eq. (11)
-
q
i
(t)
diagonal elements ofm×m matrixQ(x, s, t)
-
Q(x, s, t)
m×m weighting matrix
-
R
universal gas constant (1.987 cal · mole–1 · K–1)
-
R(x, s, t)
n×n weighting matrix
-
R
i
(t)
n×n weighting matrix
-
s
dimensionless spatial variable
-
S(x, s, t)
matrix defined in Eq. (11)
-
t
dimensionless time variable
-
T(, )
temperature, K
-
u(x, t)
n-dimensional state vector
-
u
c
(t)
wall temperature
-
u
d
desired value ofu
1(1,t)
-
u
c
*
reference control value ofu
c
-
u
c
max
maximum value ofu
c
-
u
c
min
minimum value of
c
-
v(x, t)
k-dimensional control vector
-
W(t)
l×l weighting matrix
-
x
dimensionless spatial variable
-
y(t)
m-dimensional observation vector
-
i
constants in approximate filter, Eqs. (49)–(52)
-
dimensionless parameter defined in Eq. (29)
-
H
heat of reaction (17500 cal · mole–1)
-
dimensionless activation energy, defined in Eq. (29)
-
(x)
Dirac delta function
-
(x, t)
m-dimensional observation noise
-
thermal conductivity (0.43×10–3 cal · cm–1 · sec–1 · K–1)
-
density (1 g · cm–3)
-
time, sec
-
dimensionless parameter defined in Eq. (29)
-
spatial variable, cm
- *
reference value
- ^
estimated value 相似文献
18.
Letf(t) = ∑a
k
e
ikt
be infinitely differentiable on R, |f(t)|<1. It is known that under these assumptions ‖n‖ converges to a finite limitl asn → ∞ (l
2 = sec(arga),a = (f′(0))2 -f″(0)). We obtain here more precise results: (i) an asymptotic series (in powers ofn
-1/2) for the Fourier coefficientsa
nk
off
n
, which holds uniformly ink asn → ∞; (ii) an asymptotic series (this time only powers ofn
-1 are present!) for ‖f
n
‖; (iii) the fact that ifi
j
f
(j)(0) is real forj = 1,2,..., 2h + 2 then ‖f
n
‖ = l + o(n
-h
),n → ∞. More generally, we obtain analogous finite asymptotic expansions whenf is assumed to be differentiable only finitely many times. 相似文献
19.
Let ??(n, m) denote the class of simple graphs on n vertices and m edges and let G ∈ ?? (n, m). There are many results in graph theory giving conditions under which G contains certain types of subgraphs, such as cycles of given lengths, complete graphs, etc. For example, Turan's theorem gives a sufficient condition for G to contain a Kk + 1 in terms of the number of edges in G. In this paper we prove that, for m = αn2, α > (k - 1)/2k, G contains a Kk + 1, each vertex of which has degree at least f(α)n and determine the best possible f(α). For m = ?n2/4? + 1 we establish that G contains cycles whose vertices have certain minimum degrees. Further, for m = αn2, α > 0 we establish that G contains a subgraph H with δ(H) ≥ f(α, n) and determine the best possible value of f(α, n). 相似文献
20.
Alaa E. Hamza 《Journal of Difference Equations and Applications》2013,19(3):233-253
We suppose that M is a closed subspace of l ∞(J, X), the space of all bounded sequences {x(n)} n?J ? X, where J ? {Z+,Z} and X is a complex Banach space. We define the M-spectrum σM (u) of a sequence u ? l ∞(J,X). Certain conditions will be supposed on both M and σM (u) to insure the existence of u ? M. We prove that if u is ergodic, such that σM (u,) is at most countable and, for every λ ? σM (u), the sequence e?iλnu(n) is ergodic, then u ? M. We apply this result to the operator difference equationu(n + 1) = Au(n) + ψ(n), n ? J,and to the infinite order difference equation Σ r k=1 ak (u(n + k) ? u(n)) + Σ s ? Z?(n ? s)u(s) = h(n), n?J, where ψ?l ∞(Z,X) such that ψ| J ? M, A is the generator of a C 0-semigroup of linear bounded operators {T(t)} t>0 on X, h ? M, ? ? l 1(Z) and ak ?C. Certain conditions will be imposed to guarantee the existence of solutions in the class M. 相似文献