首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 31 毫秒
1.
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).  相似文献   

2.
We present a new condition on the degree sums of a graph that implies the existence of a long cycle. Let c(G) denote the length of a longest cycle in the graph G and let m be any positive integer. Suppose G is a 2-connected graph with vertices x1,…,xn and edge set E that satisfies the property that, for any two integers j and k with j < k, xjxk ? E, d(xi) ? j and d(xk) ? K - 1, we have (1) d(xi) + d(xk ? m if j + k ? n and (2) if j + k < n, either m ? n or d(xj) + d(xk) ? min(K + 1,m). Then c(G) ? min(m, n). This result unifies previous results of J.C. Bermond and M. Las Vergnas, respectively.  相似文献   

3.
Let G be a simple connected graph of order n with degree sequence (d 1, d 2, …, d n ). Denote ( α t) i = Σ j: ij d j α , ( α m) i = ( α t) i /d i α and ( α N) i = Σ j: ij ( α t) j , where α is a real number. Denote by λ1(G) and μ1(G) the spectral radius of the adjacency matrix and the Laplacian matrix of G, respectively. In this paper, we present some upper and lower bounds of λ1(G) and μ1(G) in terms of ( α t) i , ( α m) i and ( α N) i . Furthermore, we also characterize some extreme graphs which attain these upper bounds. These results theoretically improve and generalize some known results.  相似文献   

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 Gn+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.  相似文献   

5.
G is any simple graph with m edges and n vertices where these vertices have vertex degrees d(1)≥d(2)≥?≥d(n), respectively. General algorithms for the exact calculation of χ(G), the chromatic number of G, are almost always of ‘branch and bound’ type; this type of algorithm requires an easily constructed lower bound for χ(G). In this paper it is shown that, for a number of such bounds (many of which are described here for the first time), the bound does not exceed cl(G) where cl(G) is the clique number of G.In 1972 Myers and Liu showed that cl(G)≥n?(n?2m?n). Here we show that cl(G)≥ n?[n?(2m?n)(1+c2v)12], where cv is the vertex degree coefficient of variation in G, that cl(G)≥ Bondy's constructive lower bound for χ(G), and that cl(G)≥n?(n?W(G)), where W(G) is the largest positive integer such that W(G)≤d(W(G)+1) [W(G)+1 is the Welsh and Powell upper bound for χ(G)]. It is also shown that cl(G)+13>n?(n?L(G))≥n?(n1) and that χ(G)≥ n?(n1); λ1 is the largest eigenvalue of A, the adjacency matrix of G, and L(G) is a newly defined single-valued function of G similar to W(G) in its construction from the vertex degree sequence of G [L(G)≥W(G)].Finally, a ‘greedy’ lower bound for cl(G) is constructed from A and it is shown that this lower bound is never less than Bondy's bound; thereafter, for 150 random graphs with varying numbers of vertices and edge densities, the values of lower bounds given in this paper are listed, thereby illustrating that this last greedily obtained lower bound is almost always better than each of the other bounds.  相似文献   

6.
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 Pmimi and deg Qnini 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.  相似文献   

7.
Let D(G)=(di,j)n×n denote the distance matrix of a connected graph G with order n, where dij is equal to the distance between vi and vj in G. The largest eigenvalue of D(G) is called the distance spectral radius of graph G, denoted by ?(G). In this paper, some graft transformations that decrease or increase ?(G) are given. With them, for the graphs with both order n and k pendant vertices, the extremal graphs with the minimum distance spectral radius are completely characterized; the extremal graph with the maximum distance spectral radius is shown to be a dumbbell graph (obtained by attaching some pendant edges to each pendant vertex of a path respectively) when 2≤kn−2; for k=1,2,3,n−1, the extremal graphs with the maximum distance spectral radius are completely characterized.  相似文献   

8.
A set W of the vertices of a connected graph G is called a resolving set for G if for every two distinct vertices u, v ∈ V (G) there is a vertex w ∈ W such that d(u, w) ≠ d(v, w). A resolving set of minimum cardinality is called a metric basis for G and the number of vertices in a metric basis is called the metric dimension of G, denoted by dim(G). For a vertex u of G and a subset S of V (G), the distance between u and S is the number min s∈S d(u, s). A k-partition Π = {S 1 , S 2 , . . . , S k } of V (G) is called a resolving partition if for every two distinct vertices u, v ∈ V (G) there is a set S i in Π such that d(u, Si )≠ d(v, Si ). The minimum k for which there is a resolving k-partition of V (G) is called the partition dimension of G, denoted by pd(G). The circulant graph is a graph with vertex set Zn , an additive group of integers modulo n, and two vertices labeled i and j adjacent if and only if i-j (mod n) ∈ C , where CZn has the property that C =-C and 0 ■ C. The circulant graph is denoted by Xn, Δ where Δ = |C|. In this paper, we study the metric dimension of a family of circulant graphs Xn, 3 with connection set C = {1, n/2 , n-1} and prove that dim(Xn, 3 ) is independent of choice of n by showing that dim(Xn, 3 ) ={3 for all n ≡ 0 (mod 4), 4 for all n ≡ 2 (mod 4). We also study the partition dimension of a family of circulant graphs Xn,4 with connection set C = {±1, ±2} and prove that pd(Xn, 4 ) is independent of choice of n and show that pd(X5,4 ) = 5 and pd(Xn,4 ) ={3 for all odd n ≥ 9, 4 for all even n ≥ 6 and n = 7.  相似文献   

9.
Let R = (r1,…, rm) and S = (s1,…, sn) be nonnegative integral vectors, and let U(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 U(R, S) is a position whose entry is the same for all matrices in U(R, S). The interchange graph G(R, S) is the graph where the vertices are the matrices in U(R, S) and where two matrices are joined by an edge provided they differ by an interchange. We prove that when 1 ≤ rin ? 1 (i = 1,…, m) and 1 ≤ sjm ? 1 (j = 1,…, n), G(R, S) is prime if and only if U(R, S) has no invariant positions.  相似文献   

10.
11.
Let S(1),…,S(n),T(1),…,T(n) be random subsets of the set [m]={1,…,m}. We consider the random digraph D on the vertex set [n] defined as follows: the arc ij is present in D whenever S(i)∩T(j)≠0?. Assuming that the pairs of sets (S(i),T(i)), 1≤in, are independent and identically distributed, we study the in- and outdegree distributions of a typical vertex of D as n,m.  相似文献   

12.
IfG is a finite group, we define its prime graph Г(G), as follows: its vertices are the primes dividing the order ofG and two verticesp, q are joined by an edge, if there is an element inG of orderpq. We denote the set of all the connected components of the graph Г(G) by T(G)=i(G), fori = 1,2, …,t(G)}, where t(G) is the number of connected components of Г(G). We also denote by π(n) the set of all primes dividingn, wheren is a natural number. Then ¦G¦ can be expressed as a product of m1, m2, …, mt(G), where mi’s are positive integers with π(mi) = πi. Thesem i s are called the order components ofG. LetOC(G) := {m 1,m 2, …,m t (G)} be the set of order components ofG. In this paper we prove that, if G is a finite group andOC(G) =OC(M), where M is a finite simple group witht(M) ≥ 2, thenG is neither Frobenius nor 2-Frobenius.  相似文献   

13.
Let G=(V(G),E(G)) be a simple graph. Given non-negative integers r,s, and t, an [r,s,t]-coloring of G is a mapping c from V(G)∪E(G) to the color set {0,1,…,k?1} such that |c(v i )?c(v j )|≥r for every two adjacent vertices v i ,v j , |c(e i )?c(e j )|≥s for every two adjacent edges e i ,e j , and |c(v i )?c(e j )|≥t for all pairs of incident vertices and edges, respectively. The [r,s,t]-chromatic number χ r,s,t (G) of G is defined to be the minimum k such that G admits an [r,s,t]-coloring. We determine χ r,s,t (K n,n ) in all cases.  相似文献   

14.
Let S={s i } i∈??? be a numerical semigroup. For s i S, let ν(s i ) denote the number of pairs (s i ?s j ,s j )∈S 2. When S is the Weierstrass semigroup of a family $\{\mathcal{C}_{i}\}_{i\in\mathbb{N}}Let S={s i } i∈ℕ⊆ℕ be a numerical semigroup. For s i S, let ν(s i ) denote the number of pairs (s i s j ,s j )∈S 2. When S is the Weierstrass semigroup of a family {Ci}i ? \mathbbN\{\mathcal{C}_{i}\}_{i\in\mathbb{N}} of one-point algebraic-geometric codes, a good bound for the minimum distance of the code Ci\mathcal{C}_{i} is the Feng and Rao order bound d ORD (C i ). It is well-known that there exists an integer m such that d ORD (C i )=ν(s i+1) for each im. By way of some suitable parameters related to the semigroup S, we find upper bounds for m and we evaluate m exactly in many cases. Further we conjecture a lower bound for m and we prove it in several classes of semigroups.  相似文献   

15.
A dominator coloring of a graph G is a proper coloring of G in which every vertex dominates every vertex of at least one color class. The minimum number of colors required for a dominator coloring of G is called the dominator chromatic number of G and is denoted by ?? d (G). In this paper we present several results on graphs with ?? d (G)?=???(G) and ?? d (G)?=???(G) where ??(G) and ??(G) denote respectively the chromatic number and the domination number of a graph G. We also prove that if ??(G) is the Mycielskian of G, then ?? d (G)?+?1?????? d (??(G))?????? d (G)?+?2.  相似文献   

16.
For given graphs G and H, the Ramsey number R(G,H) is the smallest natural number n such that for every graph F of order n: either F contains G or the complement of F contains H. In this paper we investigate the Ramsey number of a disjoint union of graphs . For any natural integer k, we contain a general upper bound, R(kG,H)?R(G,H)+(k-1)|V(G)|. We also show that if m=2n-4, 2n-8 or 2n-6, then R(kSn,Wm)=R(Sn,Wm)+(k-1)n. Furthermore, if |Gi|>(|Gi|-|Gi+1|)(χ(H)-1) and R(Gi,H)=(χ(H)-1)(|Gi|-1)+1, for each i, then .  相似文献   

17.
A partial orthomorphism of ${\mathbb{Z}_{n}}$ is an injective map ${\sigma : S \rightarrow \mathbb{Z}_{n}}$ such that ${S \subseteq \mathbb{Z}_{n}}$ and ??(i)?Ci ? ??(j)? j (mod n) for distinct ${i, j \in S}$ . We say ?? has deficit d if ${|S| = n - d}$ . Let ??(n, d) be the number of partial orthomorphisms of ${\mathbb{Z}_{n}}$ of deficit d. Let ??(n, d) be the number of partial orthomorphisms ?? of ${\mathbb{Z}_n}$ of deficit d such that ??(i) ? {0, i} for all ${i \in S}$ . Then ??(n, d) =???(n, d)n 2/d 2 when ${1\,\leqslant\,d < n}$ . Let R k, n be the number of reduced k ×?n Latin rectangles. We show that $$R_{k, n} \equiv \chi (p, n - p)\frac{(n - p)!(n - p - 1)!^{2}}{(n - k)!}R_{k-p,\,n-p}\,\,\,\,(\rm {mod}\,p)$$ when p is a prime and ${n\,\geqslant\,k\,\geqslant\,p + 1}$ . In particular, this enables us to calculate some previously unknown congruences for R n, n . We also develop techniques for computing ??(n, d) exactly. We show that for each a there exists??? a such that, on each congruence class modulo??? a , ??(n, n-a) is determined by a polynomial of degree 2a in n. We give these polynomials for ${1\,\leqslant\,a\,\leqslant 6}$ , and find an asymptotic formula for ??(n, n-a) as n ?? ??, for arbitrary fixed a.  相似文献   

18.
It is shown that if r = 2, then for all m, n, h ≥ 3 and all “large enough” R, W such that mR = nW, there is a tactical configuration of rank 2 girth g = 2h, and degrees m and n on sets of cardinalities R and W. We also show that if r ≥ 3 then for all h and all compatible degree sets N = {n(i, j)≥3} and all large enough numbers R(1), R(2),…, R(r) satisfying R(i)n(i, j) = R(j)n(j, i) there is a tactical configuration of rank r, girth h, and degrees N on set with cardinalities R(1), R(2),…, R(r).  相似文献   

19.
A sequence d=(d1,d2,…,dn) is graphic if there is a simple graph G with degree sequence d, and such a graph G is called a realization of d. A graphic sequence d is line-hamiltonian if d has a realization G such that L(G) is hamiltonian, and is supereulerian if d has a realization G with a spanning eulerian subgraph. In this paper, it is proved that a nonincreasing graphic sequence d=(d1,d2,…,dn) has a supereulerian realization if and only if dn≥2 and that d is line-hamiltonian if and only if either d1=n−1, or ∑di=1di≤∑dj≥2(dj−2).  相似文献   

20.
Let Wk(A) denote the k-numerical range of an n × n matrix A. It is known that Wi(A) ? Wj(A) for 1 ? j? i? n. It this paper we derive more general inclusion relations of the form ΣniλiWi(A) ? ΣniμiWi(A), where λi, μi are real coefficients.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号