A graph G is (k1, k2, …, kt)-saturated if there exists a coloring C of the edges of G in t colors 1, 2, …, t in such a way that there is no monochromatic complete ki-subgraph K of color i, 1 ? i ? t, but the addition of any new edge of color i, joining two nonadjacent vertices in G, with C, creates a monochromatic K of color i, 1 ? i ? t. We determine the maximum and minimum number of edges in such graphs and characterize the unique extremal graphs. 相似文献
LetK1,…Kn be convex sets inRd. For 0≦i denote byfithe number of subsetsS of {1,2,…,n} of cardinalityi+1 that satisfy ∩{Ki∶i∈S}≠Ø. We prove:Theorem.If fd+r=0 for somer r>=0, then {fx161-1} This inequality was conjectured by Katchalski and Perles. Equality holds, e.g., ifK1=…=Kr=Rd andKr+1,…,Kn aren?r hyperplanes in general position inRd. The proof uses multilinear techniques (exterior algebra). Applications to convexity and to extremal set theory are given. 相似文献
Let G be a graph of order n such that \(\sum_{i=0}^{n}(-1)^{i}a_{i}\lambda^{n-i}\) and \(\sum_{i=0}^{n}(-1)^{i}b_{i}\lambda^{n-i}\) are the characteristic polynomials of the signless Laplacian and the Laplacian matrices of G, respectively. We show that ai≥bi for i=0,1,…,n. As a consequence, we prove that for any α, 0<α≤1, if q1,…,qn and μ1,…,μn are the signless Laplacian and the Laplacian eigenvalues of G, respectively, then \(q_{1}^{\alpha}+\cdots+q_{n}^{\alpha}\geq\mu_{1}^{\alpha}+\cdots+\mu _{n}^{\alpha}\). 相似文献
Consider a family of stars. Take a new vertex. Join one end-vertex of each star to this new vertex. The tree so obtained is known as abanana tree. It is proved that the banana trees corresponding to the family of stars
Edge-colorings of multigraphs are studied where a generalization of Ramsey numbers is given. Let ${M_n^{(r)}}$ be the multigraph of order n, in which there are r edges between any two different vertices. Suppose q1, q2, . . . , qk and r are positive integers, and qi ≥ 2(1 ≤ i ≤ k), k > r. Let the multigraph Ramsey number ${f^{(r)} (q_1 ,q_2 , \ldots ,q_k )}$ be the minimum positive integer n such that in any k-edge coloring of ${M_n^{(r)}}$ (every edge is colored with one among k given colors, and edges between the same pair of vertices are colored with different colors), there must be ${i \in \{1,2,\ldots,k\}}$ such that ${M_n^{(r)}}$ has such a complete subgraph of order qi, of which all the edges are in color i. By Ramsey’s theorem it is easy to show ${f^{(r)} (q_1 ,q_2 , \ldots ,q_k )}$ exists for given q1 ,q2, . . . , qk and r. Lower and upper bounds for some multigraph Ramsey numbers are given. 相似文献
In this paper, we study integral operators of the form Tαf(x)=∫Rn|x-A1y|-α1 ··· |x-Amy|-αmf(y)dy,where Ai are certain invertible matrices, αi 0, 1 ≤ i ≤ m, α1 + ··· + αm = n-α, 0 ≤α n. For 1/q = 1/p-α/n , we obtain the Lp (Rn, wp)-Lq(Rn, wq) boundedness for weights w in A(p, q) satisfying that there exists c 0 such that w(Aix) ≤ cw(x), a.e. x ∈ Rn , 1 ≤ i ≤ m.Moreover, we obtain theappropriate weighted BMO and weak type estimates for certain weights satisfying the above inequality. We also give a Coifman type estimate for these operators. 相似文献
A tree is called starlike if it has exactly one vertex of degree greater than two. In [4] it was proved that two starlike treesG andH are cospectral if and only if they are isomorphic. We prove here that there exist no two non-isomorphic Laplacian cospectral starlike trees. Further, letG be a simple graph of ordern with vertex setV(G)={1,2, …,n} and letH={H1,H2, ...Hn} be a family of rooted graphs. According to [2], the rooted productG(H) is the graph obtained by identifying the root ofHi with thei-th vertex ofG. In particular, ifH is the family of the paths $P_{k_1 } , P_{k_2 } , ..., P_{k_n } $ with the rooted vertices of degree one, in this paper the corresponding graphG(H) is called the sunlike graph and is denoted byG(k1,k2, …,kn). For any (x1,x2, …,xn) ∈I*n, whereI*={0,1}, letG(x1,x2, …,xn) be the subgraph ofG which is obtained by deleting the verticesi1, i2, …,ij∈ V(G) (0≤j≤n), provided that $x_{i_1 } = x_{i_2 } = ... = x_{i_j } = 0$ . LetG(x1,x2,…, xn] be the characteristic polynomial ofG(x1,x2,…, xn), understanding thatG[0, 0, …, 0] ≡ 1. We prove that $$G[k_1 , k_2 ,..., k_n ] = \Sigma _{x \in ^{I_ * ^n } } \left[ {\Pi _{i = 1}^n P_{k_i + x_i - 2} (\lambda )} \right]( - 1)^{n - (\mathop \Sigma \limits_{i = 1}^n x_i )} G[x_1 , x_2 , ..., x_n ]$$ where x=(x1,x2,…,xn);G[k1,k2,…,kn] andPn(γ) denote the characteristic polynomial ofG(k1,k2,…,kn) andPn, respectively. Besides, ifG is a graph with λ1(G)≥1 we show that λ1(G)≤λ1(G(k1,k2, ...,kn)) < for all positive integersk1,k2,…,kn, where λ1 denotes the largest eigenvalue. 相似文献
For positive integers n1, n2, …, nI and graphs GI+1, GI+2, …, Gk, 1 ≤ / < k, the mixed Ramsey number χ(n1, …, n1, GI+1, …, Gk) is define as the least positive integer p such that for each factorization Kp = F1⊕ … ⊕ F⊕ FI+1⊕ … ⊕ Fk, it it follows that χ(Fi) ≥ ni for some i, 1 ? i ? l, or Gi is a subgraph of Fi for some i, l < i ? k. Formulas are presented for maxed Ramsey numbers in which the graphs GI+1, GI+2, …, Gk are connected, and in which k = I+1 and GI+1 is arbitray. 相似文献
Given a graphG, letB be the family of strong orientations ofG, and define A pair {p,q} of integers is called aco-pair if 1 p q
. A multiset {p, q, r} of positive integers is called aco-triple if {p, q} and {p, r} are co-pairs. LetK(p1, p2,..., pn) denote the completen-partite graph havingpi vertices in theith partite set.In this paper, we show that if {p1, p2,...,pn} can be partitioned into co-pairs whenn is even, and into co-pairs and a co-triple whenn is odd, then(K(p1, p2,..., pn)) = 2 provided that (n,p1, p2, p3, p4) (4, 1, 1, 1, 1). This substantially extends a result of Gutin [3] and a result of Koh and Tan [4]. 相似文献
Let Xi, i = 1, 2,…, be i.i.d. symmetric random variables in the domain of attraction of a symmetric stable distribution Gα with 0 < α < 2. Let Yi, i = 1, 2, …, be i.i.d. symmetric stable random variables with the common distribution Gα. It is known that under certain conditions the sequences {Xi} and {Yi} can be reconstructed on a new probability space without changing the distribution of each such that \documentclass{article}\pagestyle{empty}\begin{document}$ \sum\limits_{i = 1}^n {(X_i - Y_i) = o(n^{1/\gamma})} $\end{document} a.s. as n → ∞, where α ≦ γ < 2 (see Stout [10]). We will give a second approximation by partial sums of i.i.d. stable (with characteristic exponent α*, α < α* ≦ 2) random variables Ui, i = 1, 2,…, n, and we will obtain strong upperbounds for the differences \documentclass{article}\pagestyle{empty}\begin{document}$ \sum\limits_{i = 1}^n {(X_i - Y_i - U_i)} $\end{document}. 相似文献