共查询到20条相似文献,搜索用时 0 毫秒
1.
Gerold Jäger 《Information Processing Letters》2011,111(19):933-940
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.
Chen Min 《Information Processing Letters》2006,99(2):47-53
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.
El?bieta Sidorowicz 《Information Processing Letters》2007,102(4):147-151
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.
Anna Fiedorowicz 《Information Processing Letters》2011,111(6):287-290
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 G′⊆G, 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 Kn−Gn 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 {Kn−Gn} 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 {Kn−Gn}. 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 Cm□Cn denote the Cartesian product of Cm and Cn, the directed cycles of length m,n?2. In this paper, we determine the exact values: γ(C2□Cn)=n; γ(C3□Cn)=n if , otherwise, γ(C3□Cn)=n+1; if , otherwise, . 相似文献
9.
Maximum number of edges joining vertices on a cube 总被引:1,自引:0,他引:1
Khaled A.S. Abdel-Ghaffar 《Information Processing Letters》2003,87(2):95-99
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.
Graham Farr 《Information Processing Letters》2008,105(4):124-130
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.
《Information Processing Letters》2014,114(1-2):45-49
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.
Konstanty Junosza-Szaniawski 《Information Processing Letters》2010,110(17):757-760
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 Cm□Cn 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 γ(Cm□Cn) when m=2,3,4. In this paper, we give a lower and upper bounds for γ(Cm□Cn). Furthermore, we prove a necessary and sufficient conditions for Cm□Cn to have an efficient dominating set. Also, we determine the exact values: γ(C5□Cn)=2n; γ(C6□Cn)=2n if n≡0(mod 3), otherwise, γ(C6□Cn)=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.
《Information Processing Letters》2014,114(12):700-702
Cayley graphs of finite cyclic group are called circulant graphs and denoted by . For with prime, we give a necessary and sufficient condition for the existence of efficient dominating sets and characterize completely all its efficient dominating sets. 相似文献
20.
Mohammad Hosseini Dolama 《Information Processing Letters》2006,98(6):247-252
An oriented k-coloring of an oriented graph G is a mapping such that (i) if xy∈E(G) then c(x)≠c(y) and (ii) if xy,zt∈E(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. 相似文献