首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 31 毫秒
1.
For a given finite monoid , let be the number of graphs on n vertices with endomorphism monoid isomorphic to . For any nontrivial monoid we prove that where and are constants depending only on with .For every k there exists a monoid of size k with , on the other hand if a group of unity of has a size k>2 then .  相似文献   

2.
This paper proves a necessary and sufficient condition for the endomorphism monoid of a lexicographic product G[H] of graphs G,H to be the wreath product of the monoids and . The paper also gives respective necessary and sufficient conditions for specialized cases such as for unretractive or triangle-free graphs G.  相似文献   

3.
An overlarge set of , denoted by , is a collection {(X?{x},Bx):xX}, where X is a (v+1)-set, each (X?{x},Bx) is a and {Bx:xX} forms a partition of all triples on X. In this paper, we give a tripling construction for overlarge sets of KTS. Our main result is that: If there exists an with a special property, then there exists an . It is obtained that there exists an for u=22n−1−1 or u=qn, where prime power q≡7 (mod 12) and m≥0,n≥1.  相似文献   

4.
In an earlier paper the authors showed that with one exception the nonorientable genus of the graph with mn−1, the join of a complete graph with a large edgeless graph, is the same as the nonorientable genus of the spanning subgraph . The orientable genus problem for with mn−1 seems to be more difficult, but in this paper we find the orientable genus of some of these graphs. In particular, we determine the genus of when n is even and mn, the genus of when n=2p+2 for p≥3 and mn−1, and the genus of when n=2p+1 for p≥3 and mn+1. In all of these cases the genus is the same as the genus of Km,n, namely ⌈(m−2)(n−2)/4⌉.  相似文献   

5.
Let G be a vertex-disjoint union of directed cycles in the complete directed graph Dt, let |E(G)| be the number of directed edges of G and suppose or if t=5, and if t=6. It is proved in this paper that for each positive integer t, there exist -decompositions for DtG if and only if .  相似文献   

6.
Generalized Steiner systems were first introduced by Etzion and used to construct optimal constant weight codes over an alphabet of size g+1 with minimum Hamming distance 2k−3, in which each codeword has length v and weight k. As to the existence of a , a lot of work has been done for k=3, while not so much is known for k=4. The notion k-GDD was first introduced by Chen et al. and used to construct . The necessary condition for the existence of a is v≥14. In this paper, it is proved that there exists a for any prime power and v≥19. By using this result, the known results on the existence of optimal quaternary constant weight codes are then extended.  相似文献   

7.
The Majority game is played by a questioner () and an answerer (). holds n elements, each of which can be labeled as 0 or 1. is trying to identify some element holds as having the Majority label or, in the case of a tie, claim there is none. To do this asks questions comparing whether two elements have the same or different label. ’s goal is to ask as few questions as possible while ’s goal is to delay as much as possible. Let q denote the minimal number of questions needed for to identify a Majority element regardless of ’s answers.In this paper we investigate upper and lower bounds for q in a variation of the Majority game, where is allowed to lie up to t times. We consider two versions of the game, the adaptive (where questions are asked sequentially) and the oblivious (where questions are asked in one batch).  相似文献   

8.
Thomassen recently proved, using the Tutte cycle technique, that if G is a 3-connected cubic triangle-free planar graph then G contains a bipartite subgraph with at least edges, improving the previously known lower bound . We extend Thomassen’s technique and further improve this lower bound to .  相似文献   

9.
The energy of a graph G, denoted by E(G), is defined as the sum of the absolute values of all eigenvalues of G. Let G be a graph of order n and be the rank of the adjacency matrix of G. In this paper we characterize all graphs with . Among other results we show that apart from a few families of graphs, , where n is the number of vertices of G, and χ(G) are the complement and the chromatic number of G, respectively. Moreover some new lower bounds for E(G) in terms of are given.  相似文献   

10.
Let be the signed edge domination number of G. In 2006, Xu conjectured that: for any 2-connected graph G of order n(n≥2), . In this article we show that this conjecture is not true. More precisely, we show that for any positive integer m, there exists an m-connected graph G such that . Also for every two natural numbers m and n, we determine , where Km,n is the complete bipartite graph with part sizes m and n.  相似文献   

11.
This paper studies the game chromatic number and game colouring number of the square of graphs. In particular, we prove that if G is a forest of maximum degree Δ≥9, then , and there are forests G with . It is also proved that for an outerplanar graph G of maximum degree Δ, , and for a planar graph G of maximum degree Δ, .  相似文献   

12.
A pair of sequences such that and
  相似文献   

13.
We study the set of annular non-crossing permutations of type B, and we introduce a corresponding set of annular non-crossing partitions of type B, where p and q are two positive integers. We prove that the natural bijection between and is a poset isomorphism, where the partial order on is induced from the hyperoctahedral group Bp+q, while is partially ordered by reverse refinement. In the case when q=1, we prove that is a lattice with respect to reverse refinement order.We point out that an analogous development can be pursued in type D, where one gets a canonical isomorphism between and . For q=1, the poset coincides with a poset “NC(D)(p+1)” constructed in a paper by Athanasiadis and Reiner [C.A. Athanasiadis, V. Reiner, Noncrossing partitions for the group Dn, SIAM Journal of Discrete Mathematics 18 (2004) 397-417], and is a lattice by the results of that paper.  相似文献   

14.
A (d,1)-total labelling of a graph G assigns integers to the vertices and edges of G such that adjacent vertices receive distinct labels, adjacent edges receive distinct labels, and a vertex and its incident edges receive labels that differ in absolute value by at least d. The span of a (d,1)-total labelling is the maximum difference between two labels. The (d,1)-total number, denoted , is defined to be the least span among all (d,1)-total labellings of G. We prove new upper bounds for , compute some for complete bipartite graphs Km,n, and completely determine all for d=1,2,3. We also propose a conjecture on an upper bound for in terms of the chromatic number and the chromatic index of G.  相似文献   

15.
In this paper, we study the distribution and simultaneous bifurcation of limit cycles bifurcated from the two periodic annuli of the holomorphic differential equation , after a small polynomial perturbation. We first show that, under small perturbations of the form , where is a polynomial of degree 2m−1 in which the power of z is odd and the power of is even, the only possible distribution of limit cycles is (u,u) for all values of u=0,1,2,…,m−3. Hence, the sharp upper bound for the number of limit cycles bifurcated from each two period annuli of is m−3, for m≥4. Then we consider a perturbation of the form , where is a polynomial of degree m in which the power of z is odd and obtain the upper bound m−5, for m≥6. Moreover, we show that the distribution (u,v) of limit cycles is possible for 0≤um−5, 0≤vm−5 with u+vm−2 and m≥9.  相似文献   

16.
We first define a transitive resolvable idempotent quasigroup (TRIQ), and show that a TRIQ of order v exists if and only if 3∣v and . Then we use TRIQ to present a tripling construction for large sets of resolvable Mendelsohn triple systems s, which improves an earlier version of tripling construction by Kang. As an application we obtain an for any integer n≥1, which provides an infinite family of even orders.  相似文献   

17.
Daqing Yang 《Discrete Mathematics》2009,309(13):4614-4623
Let be a directed graph. A transitive fraternal augmentation of is a directed graph with the same vertex set, including all the arcs of and such that for any vertices x,y,z,
1.
if and then or (fraternity);
2.
if and then (transitivity).
In this paper, we explore some generalization of the transitive fraternal augmentations for directed graphs and its applications. In particular, we show that the 2-coloring number col2(G)≤O(1(G)0(G)2), where k(G) (k≥0) denotes the greatest reduced average density with depth k of a graph G; we give a constructive proof that k(G) bounds the distance (k+1)-coloring number colk+1(G) with a function f(k(G)). On the other hand, k(G)≤(col2k+1(G))2k+1. We also show that an inductive generalization of transitive fraternal augmentations can be used to study nonrepetitive colorings of graphs.  相似文献   

18.
We take up the existence and global behavior of positive continuous solutions of the following nonlinear parabolic equation in (n?2) with boundary conditions u=0 on and u(x,0)=u0(x). The nonlinear term is required to satisfy some conditions related to a functional class , which we introduce in this paper and will be called parabolic Kato class in the half space. Our approach is based on potential theory.  相似文献   

19.
Write a≡3⋅2−1 and where p is an odd prime. Let c be a value that is congruent (modp) to either a or b. For any x from Zp?{0}, evaluate each of x and within the interval (0,p). Then consider the quantity where the differences are evaluated in the interval (0,p−1), and the quantity where the differences are evaluated (modp+1) in the interval (0,p+1). As x varies over Zp?{0}, the values of each of and give exactly two occurrences of nearly every member of 1,2,…,(p−1)/2. This fact enables a and b to be used in constructing some terraces for Zp−1 and Zp+1 from segments of elements that are themselves initially evaluated in Zp.  相似文献   

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

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