If G is a graph with p vertices and at least one edge, we set φ (G) = m n max |f(u) ? f(v)|, where the maximum is taken over all edges uv and the minimum over all one-to-one mappings f : V(G) → {1, 2, …, p}: V(G) denotes the set of vertices of G.Pn will denote a path of length n whose vertices are integers 1, 2, …, n with i adjacent to j if and only if |i ? j| = 1. Pm × Pn will denote a graph whose vertices are elements of {1, 2, …, m} × {1, 2, …, n} and in which (i, j), (r, s) are adjacent whenever either i = r and |j ? s| = 1 or j = s and |i ? r| = 1.Theorem.If max(m, n) ? 2, thenφ(Pm × Pn) = min(m, n). 相似文献
For a graph G, letG′(G″) denote an orientation ofG having maximum (minimum respectively) finite diameter. We show that the length of the longest path in any 2-edge connected (undirected) graph G is precisely diam(G′). LetK(ml,m2,...,mn) be the completen-partite graph with parts of cardinalitiesm1 m2, …,mn. We prove that ifm1 = m2 = … =mn = m,n ≥ 3, then diam(K″(m1,m2,...,mn)) = 2, unless m=1 andn = 4. 相似文献
Let G be a finitely presented group given by its pre-abelian presentation <X1,…,Xm; Xe11ζ1,…,Xemmζ,ζm+1,…>, where ei≥0 for i = 1,…, m and ζj?G′ for j≥1. Let N be the subgroup of G generated by the normal subgroups [xeii, G] for i = 1,…, m. Then Dn+2(G)≡γn+2(G) (modNG′) for all n≥0, where G” is the second commutator subgroup of G,γn+2(G) is the (n+2)th term of the lower central series of G and Dn+2(G) = G∩(1+△n+2(G)) is the (n+2)th dimension subgroup of G. 相似文献
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. 相似文献
We deal with the problem of representing several abstract groups simultaneously by one graph as automorphism groups of its powers. We call subgroups Γ1,…, Γn of a finite group Γ representable iff there is a graph G and an injective mapping φ from ∪i=1nΓi into the symmetric group on V(G) such that for i=1,…, nφ|Γi is a monomorphism onto Aut Gi. We give a necessary and a sufficient condition for groups being representable, the latter implying, e.g., that finite groups Γ1≤…≤Γn are representable. 相似文献
Let R = (r1,…, rm) and S = (s1,…, sn) be nonnegative integral vectors, and let (R, S) denote the class of all m × n matrices of 0's and 1's having row sum vector R and column sum vector S. An invariant position of (R, S) is a position whose entry is the same for all matrices in (R, S). The interchange graph G(R, S) is the graph where the vertices are the matrices in (R, S) and where two matrices are joined by an edge provided they differ by an interchange. We prove that when 1 ≤ ri ≤ n ? 1 (i = 1,…, m) and 1 ≤ sj ≤ m ? 1 (j = 1,…, n), G(R, S) is prime if and only if (R, S) has no invariant positions. 相似文献
Let R(Γ, G) be the variety of representations of a finitely generated group Γ in a simple complex algebraic group G. We establish some sufficient conditions for the image of the diagonal representation ϱ = (ϱ1, …, ϱt), ϱi ε R(Γ, G), to be dense in Gf in the complex topology (“weak approximation”). 相似文献
Given a triple (G, W, γ) of an open bounded set G in the complex plane, a weight function W(z) which is analytic and different from zero in G, and a number γ with 0 ≤ γ ≤ 1, we consider the problem of locally uniform rational approximation of any function ƒ(z), which is analytic in G, by weighted rational functions Wmi+ni(z)Rmi, ni(z)i = 0∞, where Rmi, ni(z) = Pmi(z)/Qni(z) with deg Pmi ≤ mi and deg Qni ≤ ni for all i ≥ 0 and where mi + ni → ∞ as i → ∞ such that lim mi/[mi + ni] = γ. Our main result is a necessary and sufficient condition for such an approximation to be valid. Applications of the result to various classical weights are also included. 相似文献
Let P(x) = Σi=0naixi be a nonnegative integral polynomial. The polynomial P(x) is m-graphical, and a multi-graph G a realization of P(x), provided there exists a multi-graph G containing exactly P(1) points where ai of these points have degree i for 0≤i≤n. For multigraphs G, H having polynomials P(x), Q(x) and number-theoretic partitions (degree sequences) π, ?, the usual product P(x)Q(x) is shown to be the polynomial of the Cartesian product G × H, thus inducing a natural product π? which extends that of juxtaposing integral multiple copies of ?. Skeletal results are given on synthesizing a multi-graph G via a natural Cartesian product G1 × … × Gk having the same polynomial (partition) as G. Other results include an elementary sufficient condition for arbitrary nonnegative integral polynomials to be graphical. 相似文献
Let A be an n × n normal matrix over , and Qm, n be the set of strictly increasing integer sequences of length m chosen from 1,…,n. For α, β ? Qm, n denote by A[α|β] the submatrix obtained from A by using rows numbered α and columns numbered β. For k ? {0, 1,…, m} we write |α∩β| = k if there exists a rearrangement of 1,…, m, say i1,…, ik, ik+1,…, im, such that α(ij) = β(ij), i = 1,…, k, and {α(ik+1),…, α(im) } ∩ {β(ik+1),…, β(im) } = ?. A new bound for |detA[α|β ]| is obtained in terms of the eigenvalues of A when 2m = n and |α∩β| = 0.Let n be the group of n × n unitary matrices. Define the nonnegative number where | α ∩ β| = k. It is proved that Let A be semidefinite hermitian. We conjecture that ρ0(A) ? ρ1(A) ? ··· ? ρm(A). These inequalities have been tested by machine calculations. 相似文献
The symbol C(m1n1m2n2...msns) denotes a 2-regular graph consisting ofni cycles of lengthmi, i=1, 2,…,s. In this paper, we give some construction methods of cyclic(Kv,G)-designs, and prove that there exists a cyclic(Kv, G)-design whenG=C((4m1)n1(4m2)n2...(4ms)ns andv ≡ 1 (mod 2¦G¦). 相似文献
Let R be a noetherian ring, and G(R) the Grothendieck group of finitely generated modules over R. For a finite abelian group π, we describe G(Rπ) as the direct sum of groups G(R'). Each R' is the form R[ζn, 1/n], where n is a positive integer and ζn a primitive nth root of unity. As an application, we describe the structure of the Grothendiek group of pairs (H, u), where H is an abelian group and u is an automorphism of H of finite order. 相似文献
If A∈T(m, N), the real-valued N-linear functions on Em, and σ∈SN, the symmetric group on {…,N}, then we define the permutation operator Pσ: T(m, N) → T(m, N) such that Pσ(A)(x1,x2,…,xN = A(xσ(1),xσ(2),…, xσ(N)). Suppose Σqi=1ni = N, where the ni are positive integers. In this paper we present a condition on σ that is sufficient to guarantee that 〈Pσ(A1?A2???Aq),A1?A2?? ? Aq〉 ? 0 for Ai∈S(m, ni), where S(m, ni) denotes the subspace of T(m, ni) consisting of all the fully symmetric members of T(m, ni). Also we present a broad generalization of the Neuberger identity which is sometimes useful in answering questions of the type described below. Suppose G and H are subgroups of SN. We let TG(m, N) denote all A∈T(m, N) such that Pσ(A) = A for all σ∈G. We define the symmetrizer G: T(m, N)→TG(m,N) such that . Suppose H is a subgroup of G and A∈TH(m, N). Clearly We are interested in the reverse type of comparison. In particular, if D is a suitably chosen subset of TH(m,N), then can we explicitly present a constant C>0 such that for all A∈D? 相似文献
LetG be a finite group and #Cent(G) denote the number of centralizers of its elements.G is calledn-centralizer if #Cent(G)=n, and primitiven-centralizer if #Cent(G)=#Cent(G/Z(G))=n. In this paper we investigate the structure of finite groups with at most 21 element centralizers. We prove that such a group is solvable and ifG is a finite group such thatG/Z(G)?A5, then #Cent(G)=22 or 32. Moroever, we prove that A5 is the only finite simple group with 22 centralizers. Therefore we obtain a characterization of A5 in terms of the number of centralizers 相似文献
A finitep-groupP is of type (m, n) ifP has nilpotency classm-1,P/P'≌Zpn×Zpn and all the lower central factorsKi(P)/Ki+1(P) are cyclic of orderpn. Our main result on finite groups with a Sylowp-subgroup of type (m, n) is (Theorem 4.1): Let G be a finite group with a Sylow p-subgroup P of type (m, n), n≧2 p≧3, m≧(n+5)(p?1)+1. For H≦G denote \(\bar H = HO_{p'} (G)/O_{p'} (G)\) . If Op (G) is not cyclic and P'1 ≠ 1, then \(\bar P \Delta \bar G\) and \(\bar G = \bar P \cdot \bar T\) is a semidirect product of \(\bar P\) and \(\bar T\) , where \(\bar T\) is cyclic of order t, t|p-1. Here P1 is the subgroup defined in section 0. This theorem easily yields that under its assumptionsNG (P)/OP (NG(P))≌G/OP (G), it gives information on the conjugacy pattern ofp-elements ofG and gives information on the structure ofp-local subgroups ofG (Theorems 4.2, 4.3 and 4.4). 相似文献
In their papers (Technical Report CS-TR 50, University of Central Florida, 1980; J. Combin. Theory Ser. B32 (1982), 90–94) Brigham and Dutton introduce the notion of (n : i)-chromatic numbers of a graph, a generalization of Stahl's nth chromatic numbers (J. Combin. Theory Ser. B20, (1976), 185–203). The (n : i)-chromatic number of a graph G, denoted by χni(G), is the smallest integer m such that each vertex of G can be colored with a set of n colors in {1, 2,…, m} in such a way that any two adjacent vertices have exactly i colors in common. Brigham and Dutton conjecture at the end of loc cit that for all integers n and i with 0 ≤ i ≤ n ? 1, and for every graph G, χni+1(G) ≤ χni(G). We prove this conjecture in some special cases and disprove it in the general case. 相似文献
Let G be a finite group G, and let N(G) be the set of sizes of its conjugacy classes. It is shown that, if N(G) equals N(Altn) or N(Symn), where n > 1361, then G has a composition factor isomorphic to an alternating group Altm with m ≤ n and the interval (m, n] contains no primes. 相似文献
For each natural number n, let a0(n) = n, and if a0(n),…,ai(n) have already been defined, let ai+1(n) > ai(n) be minimal with (ai+1(n), a0(n) … ai(n)) = 1. Let g(n) be the largest ai(n) not a prime or the square of a prime. We show that g(n) ~ n and that for some c > 0. The true order of magnitude of g(n) ? n seems to be connected with the fine distribution of prime numbers. We also show that “most” ai(n) that are not primes or squares of primes are products of two distinct primes. A result of independent interest comes of one of our proofs: For every sufficiently large n there is a prime with [] composite. 相似文献
Let G be a finite simple graph on a vertex set V(G) = {x11,…, xn1}. Also let m1,…, mn ≥ 2 be integers and G1,…, Gn be connected simple graphs on the vertex sets V(Gi) = {xi1,…, ximi}. In this article, we provide necessary and sufficient conditions on G1,…, Gn for which the graph obtained by attaching the Gi to G is unmixed or vertex decomposable. Then we characterize Cohen–Macaulay and sequentially Cohen–Macaulay graphs obtained by attaching the cycle graphs or connected chordal graphs to arbitrary graphs. 相似文献
The interval number i(G) of a graph G with n vertices is the lowest integer m such that G is the intersection graph of some family of sets I1,…,In with every Ii being the union of at most m real intervals. In this article a lower bound for i(G) is proved followed by some considerations about the construction of graphs that are critical with respect to the interval number. 相似文献