首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 31 毫秒
1.
Mastermind is a famous two-player game, where the codemaker has to choose a secret code and the codebreaker has to guess it in as few questions as possible using information he receives from the codemaker after each guess. In Generalized Black-peg Mastermind for given arbitrary numbers p, c, the secret code consists of p pegs each having one of c colors, and the received information consists only of a number of black pegs, where this number equals the number of pegs matching in the corresponding question and the secret code. Let b(p,c) be the pessimistic number of questions for Generalized Black-peg Mastermind. By a computer program we compute several values b(p,c). By introducing some auxiliary games and combining this program with theoretical methods, for arbitrary c we obtain exact formulas for b(2,c), b(3,c) and b(4,c) and give upper and lower bounds for b(5,c) and a lower bound for b(6,c). Furthermore, for arbitrary p, we present upper bounds for b(p,2), b(p,3) and b(p,4). Finally, we give bounds for the general case b(p,c). In particular, we improve an upper bound recently proved by Goodrich.  相似文献   

2.
We prove that the game chromatic and the game colouring number of the class of orientations of cactuses with girth of 2 or 3 is 4. We improve this bound for the class of orientations of certain forest-like cactuses to the value of 3. These results generalise theorems on the game colouring number of undirected forests (Faigle et al., 1993 [3]) resp. orientations of forests (Andres, 2009 [1]). For certain undirected cactuses with girth 4 we also obtain the tight bound 4, thus improving a result of Sidorowicz (2007) [8].  相似文献   

3.
A 2-dipath k-coloring f of an oriented graph is a mapping from to the color set {1,2,…,k} such that f(x)≠f(y) whenever two vertices x and y are linked by a directed path of length 1 or 2. The 2-dipath chromatic number of is the smallest k such that has a 2-dipath k-coloring. In this paper we prove that if is an oriented Halin graph, then . There exist infinitely many oriented Halin graphs such that .  相似文献   

4.
Guillotine partitions play an important role in many research areas and application domains, e.g., computational geometry, computer graphics, integrated circuit layout, and solid modeling, to mention just a few. In this paper we present an exact summation formula for the number of structurally-different guillotine partitions in d dimensions by n hyperplanes, and then show that it is .  相似文献   

5.
We consider the colouring game and the marking game. A graph G is a cactus if any two cycles of G have at most one common vertex. We prove that χg(C)=colg(C)=5 for family of cactuses C.  相似文献   

6.
Let G be any finite graph. A mapping c:E(G)→{1,…,k} is called an acyclic edge k-colouring of G, if any two adjacent edges have different colours and there are no bichromatic cycles in G. In other words, for every pair of distinct colours i and j, the subgraph induced in G by all the edges that have colour i or j is acyclic. The smallest number k of colours such that G has an acyclic edge k-colouring is called the acyclic chromatic index of G and is denoted by .Determining the acyclic chromatic index of a graph is a hard problem, both from theoretical and algorithmical point of view. In 1991, Alon et al. proved that for any graph G of maximum degree Δ(G). This bound was later improved to 16Δ(G) by Molloy and Reed. In general, the problem of computing the acyclic chromatic index of a graph is NP-complete. Only a few algorithms for finding acyclic edge colourings have been known by now. Moreover, these algorithms work only for graphs from particular classes.In our paper, we prove that for every graph G which satisfies the condition that |E(G)|?t|V(G)|−1 for each subgraph GG, where t?2 is a given integer, the constant p=2t3−3t+2. Based on that result, we obtain a polynomial algorithm which computes such a colouring. The class of graphs covered by our theorem is quite rich, for example, it contains all t-degenerate graphs.  相似文献   

7.
In this paper we propose a limit characterization of the behaviour of classes of graphs with respect to their number of spanning trees. Let {Gn} be a sequence of graphs G0,G1,G2,… that belong to a particular class. We consider graphs of the form KnGn that result from the complete graph Kn after removing a set of edges that span Gn. We study the spanning tree behaviour of the sequence {KnGn} when n→∞ and the number of edges of Gn scales according to n. More specifically, we define the spanning tree indicator ({Gn}), a quantity that characterizes the spanning tree behaviour of {KnGn}. We derive closed formulas for the spanning tree indicators for certain well-known classes of graphs. Finally, we demonstrate that the indicator can be used to compare the spanning tree behaviour of different classes of graphs (even when their members never happen to have the same number of edges).  相似文献   

8.
Let γ(G) denote the domination number of a digraph G and let CmCn denote the Cartesian product of Cm and Cn, the directed cycles of length m,n?2. In this paper, we determine the exact values: γ(C2Cn)=n; γ(C3Cn)=n if , otherwise, γ(C3Cn)=n+1; if , otherwise, .  相似文献   

9.
Maximum number of edges joining vertices on a cube   总被引:1,自引:0,他引:1  
Let Ed(n) be the number of edges joining vertices from a set of n vertices on a d-dimensional cube, maximized over all such sets. We show that Ed(n)=∑i=0r−1(li/2+i)2li, where r and l0>l1>?>lr−1 are nonnegative integers defined by n=∑i=0r−12li.  相似文献   

10.
We use transfer matrix methods to determine bounds for the numbers of legal Go positions for various numbers of players on some planar lattice graphs, including square lattice graphs such as those on which the game is normally played. We also find bounds on limiting constants that describe the behaviour of the number of legal positions on these lattice graphs as the dimensions of the lattices tend to infinity. These results amount to giving bounds for some specific evaluations of Go polynomials on these graphs.  相似文献   

11.
The oriented chromatic number of an oriented graph G is the minimum order of an oriented graph H such that G admits a homomorphism to H. The oriented chromatic number of an unoriented graph G is the maximal chromatic number over all possible orientations of G. In this paper, we prove that every Halin graph has oriented chromatic number at most 8, improving a previous bound by Hosseini Dolama and Sopena, and confirming the conjecture given by Vignal.  相似文献   

12.
In this paper, we focus on the oriented coloring of graphs. Oriented coloring is a coloring of the vertices of an oriented graph G without symmetric arcs such that (i) no two neighbors in G are assigned the same color, and (ii) if two vertices u and v such that (u,v)∈A(G) are assigned colors c(u) and c(v), then for any (z,t)∈A(G), we cannot have simultaneously c(z)=c(v) and c(t)=c(u). The oriented chromatic number of an unoriented graph G is the smallest number k of colors for which any of the orientations of G can be colored with k colors.The main results we obtain in this paper are bounds on the oriented chromatic number of particular families of planar graphs, namely 2-dimensional grids, fat trees and fat fat trees.  相似文献   

13.
14.
We consider the coloring game and the marking game on graphs with bounded number of cycles passing through any edge. We prove that the game coloring number of a graph G is at most c+4, if every edge of G belongs to at most c different cycles. This result covers two earlier bounds on the game coloring number: for trees (c=0) and for cactuses (c=1).  相似文献   

15.
Let G be a simple and undirected graph. By mi(G) we denote the number of maximal independent sets in G. Erd?s and Moser posed the problem to determine the maximum cardinality of mi(G) among all graphs of order n and to characterize the corresponding extremal graphs attaining this maximum cardinality. The above problem has been solved by Moon and Moser in [J.W. Moon, L. Moser, On cliques in graphs, Israel J. Math. 3 (1965) 23-28]. More recently, Jin and Li [Z. Jin, X. Li, Graphs with the second largest number of maximal independent sets, Discrete Mathematics 308 (2008) 5864-5870] investigated the second largest cardinality of mi(G) among all graphs of order n and characterized the extremal graph attaining this value of mi(G). In this paper, we shall determine the third largest cardinality of mi(G) among all graphs G of order n. Additionally, graphs achieving this value are also determined.  相似文献   

16.
We are interested in finding bounds for the distant-2 chromatic number of geometric graphs drawn from different models. We consider two undirected models of random graphs: random geometric graphs and random proximity graphs for which sharp connectivity thresholds have been shown. We are interested in a.a.s. connected graphs close just above the connectivity threshold. For such subfamilies of random graphs we show that the distant-2-chromatic number is Θ(logn) with high probability. The result on random geometric graphs is extended to the random sector graphs defined in [J. Díaz, J. Petit, M. Serna. A random graph model for optical networks of sensors, IEEE Transactions on Mobile Computing 2 (2003) 143-154].  相似文献   

17.
Domination number of Cartesian products of directed cycles   总被引:1,自引:0,他引:1  
Let γ(G) denote the domination number of a digraph G and let CmCn denote the Cartesian product of Cm and Cn, the directed cycles of length m,n?2. In Liu et al. (2010) [11], we determined the exact values of γ(CmCn) when m=2,3,4. In this paper, we give a lower and upper bounds for γ(CmCn). Furthermore, we prove a necessary and sufficient conditions for CmCn to have an efficient dominating set. Also, we determine the exact values: γ(C5Cn)=2n; γ(C6Cn)=2n if n≡0(mod 3), otherwise, γ(C6Cn)=2n+2; if m≡0(mod 3) and n≡0(mod 3).  相似文献   

18.
The bondage number of a digraph D is the minimum number of arcs whose removal results in a new digraph with larger domination number. In this paper, we determine the bondage number in complete t-partite digraph .  相似文献   

19.
Cayley graphs of finite cyclic group Zn are called circulant graphs and denoted by Cay(Zn,S). For Cay(Zn,S) with n|S|+1 prime, we give a necessary and sufficient condition for the existence of efficient dominating sets and characterize completely all its efficient dominating sets.  相似文献   

20.
An oriented k-coloring of an oriented graph G is a mapping such that (i) if xyE(G) then c(x)≠c(y) and (ii) if xy,ztE(G) then c(x)=c(t)⇒c(y)≠c(z). The oriented chromatic number of an oriented graph G is defined as the smallest k such that G admits an oriented k-coloring. We prove in this paper that every Halin graph has oriented chromatic number at most 9, improving a previous bound proposed by Vignal.  相似文献   

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

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