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

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

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

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

7.
8.
Suppose that G is a planar graph with maximum degree Δ and without intersecting 4-cycles, that is, no two cycles of length 4 have a common vertex. Let χ(G), and denote the total chromatic number, list edge chromatic number and list total chromatic number of G, respectively. In this paper, it is proved that χ(G)=Δ+1 if Δ≥7, and and if Δ(G)≥8. Furthermore, if G is a graph embedded in a surface of nonnegative characteristic, then our results also hold.  相似文献   

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

10.
On edge domination numbers of graphs   总被引:1,自引:0,他引:1  
Let and be the signed edge domination number and signed star domination number of G, respectively. We prove that holds for all graphs G without isolated vertices, where n=|V(G)|?4 and m=|E(G)|, and pose some problems and conjectures.  相似文献   

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

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