Search

Abstract: For a given graph G of order n, a k--labelling is defined as a function such that when and when . The -labelling number of G, denoted by , is the smallest number k such that G has a k--labelling. The hole index of G is the minimum number of integers not used in a --labelling of G. We say G is full-colorable if ; otherwise, it will be called non-full colorable. In this paper, we consider the graphs with and , where m is a positive integer. Our main work generalized a result by Fishburn and Roberts [No-hole -colorings, Discrete Appl. Math. 130 (2003) 513–519]. [Copyright &y& Elsevier]

Given a sequence of n arbitrary events in a probability space, we assume that the individual probabilities as well as some or all joint probabilities of up to m events are known, where m. Using this information we give lower and upper bounds for the probability of the union. The bounds are obtained as optimum values of linear programming problems or objective function values corresponding to feasible solutions of the dual problems. If all joint probabilities of the k-tuples of events are known, for k not exceeding m, then the LP is the large-scale Boolean probability bounding problem. Another type of LP is the binomial moment problem, where we assume the knowledge of some of the binomial moments of the number of events which occur. The two LPs can be obtained from each other by aggregation/disaggregation procedures. In this paper, we define LPs which are obtained by partial aggregation/disaggregation from these two LPs. This way we can keep the size of the problem low but can produce very good bounds in many cases. The obtained lower bounds generalize the bounds of de Caen (Discrete Math. 169 (1997) 217) and Kuai, Alajaji and Takahara (Discrete Appl. Math. 215 (2000) 147). Practical applications are mentioned and numerical examples are presented. [Copyright &y& Elsevier]