In this paper we present theoretical and algorithmic results for the computation of lower bounds on the chromatic number of a weighted graph. In particular, we study different ways of a possible improvement of the lower bound offered by a maximum weighted clique. Based on our findings we devise new algorithms and show their performance on random graphs.
In [3], the present author used a binary operation as a tool for characterizing geodetic graphs. In this paper a new proof of the main result of the paper cited above is presented. The new proof is shorter and simpler.
Impartial Solitaire Clobber is a one-player version of the combinatorial game Clobber, introduced by Albert et al. in 2002. The initial configuration of Impartial Solitaire Clobber is a graph, such that there is a stone placed on each of its vertex, each stone being black or white. A move of the game consists in picking a stone, and clobbering an adjacent stone of the opposite color. By clobbering we mean that the clobbered stone is removed from the graph, and replaced by the clobbering one....
For a graph G of order n we consider the unique partition of its vertex set V(G) = A ∪ B with A = {v ∈ V(G): d(v) ≥ n/2} and B = {v ∈ V(G):d(v) < n/2}. Imposing conditions on the vertices of the set B we obtain new sufficient conditions for hamiltonian and pancyclic graphs.
∗ This work has been partially supported by the Bulgarian NSF under Contract No. I-506/1995.In this note we construct five new symmetric 2-(61,16,4) designs invariant under the dihedral group of order 10. As a by-product we obtain 25 new residual 2-(45,12,4) designs. The automorphism groups of all new designs are computed.
2000 Mathematics Subject Classification: 05C55.For a given graph G let V(G) and E(G) denote the vertex and the edge set of G respevtively. The symbol G e → (a1, …, ar) means that in every r-coloring of E(G) there exists a monochromatic ai-clique of color i for some i ∈ {1,…,r}. The edge Folkman numbers are defined by the equality Fe(a1, …, ar; q) = min{|V(G)| : G e → (a1, …, ar; q) and cl(G) < q}. In this paper we prove a new upper bound on the edge Folkman number Fe(3,5;13), namely Fe(3,5;13)...
The maximal cardinality of a code W on the unit sphere in n dimensions with (x, y) ≤ s whenever x, y ∈ W, x 6= y, is denoted by A(n, s). We use two methods for obtaining new upper bounds on A(n, s) for some values of n and s. We find new linear programming bounds by suitable polynomials of degrees which are higher than the degrees of the previously known good polynomials due to Levenshtein [11, 12]. Also we investigate the possibilities for attaining the Levenshtein bounds [11, 12]. In such cases...
We show that any total n-functional digraph D is uniquely determined by its skeleton up to the orientation of some cycles and infinite chains. Next, we characterize all graphs G such that each n-functional digraph obtained from G by directing all its edges is total. Finally, we describe finite graphs whose edges can be directed to form a total n-functional digraph without cycles.