Search

Considering the partitions of a set into nonempty subsets, we obtain an expression for the number of all partitions of a given type. The chromatic polynomial of a graph subdivision is generalized, considering two sets of colors, and a general explicit expression is obtained for this generalization. Using these results, we determine the generalized chromatic polynomial for the particular case of complete graph subdivision. [ABSTRACT FROM AUTHOR]

We show that the class of graphs with quadratic stability number is not hereditary. Then we prove that this class contains a unique maximal hereditary subclass and, finally, we characterize this subclass by two forbidden induced subgraphs. [ABSTRACT FROM AUTHOR]

Let p and t, p ≥ t, be positive integers. A t-composition of p is an ordered t-tuple of positive integers summing p. If T = ( s , s , . . . , s) is a t-composition p and W is a p − ( t − 1) × t matrix, then $ W(T) = \sum\limits_{k = 1}^t {{w_{{s_k}k}}} $ is called the weight of the t-composition T. We show that finding a minimum weight t-composition of p can be reduced to the determination of the shortest path in a certain digraph with O( tp) vertices. This study was motivated by a problem arising from the automobile industry, and the presented result is useful when dealing with huge location problems. [ABSTRACT FROM AUTHOR]