Let \(G = (X, E)\) be any graph. Then \(D \subset X\) is called a dominating set of \(G\) if for every vertex \(x \in X – D\), \(x\) is adjacent to at least one vertex of \(D\). The domination number, \(\gamma(G)\), is \(\min \{|D| \mid D\) { is a dominating set of } \(G\}\). In 1965 Vizing gave the following conjecture: For any two graphs \(G\) and \(H\)

\[\gamma(G \times H) \geq \gamma(G) . \gamma(H).\]

In this paper, it is proved that \(\gamma(G \times H) > \gamma(G) . \gamma(H)\) if \(H\) is either one of the following graphs: (a) \(H = G^-\), i.e., complementary graph of \(G\), (b) \(H = C_m\), i.e., a cycle of length \(m\) or (c) \(\gamma(H) \leq 2\).

In [1],[2], there are many assignment models. This paper gives a new assignment model and an algorithm for solving this problem.

Let \(v, k\), and \(n\) be positive integers. An incomplete perfect Mendelsohn design, denoted by \(k\)-IMPD\((v, n)\), is a triple \((X, Y, B)\) where \(S\) is a \(v\)-set (of points), \(Y\) is an \(n\)-subset of \(X\), and \(B\) is a collection of cyclically ordered \(k\)-subsets of \(X\) (called blocks) such that every ordered pair \((a, b) \in (X \times X) \setminus (Y \times Y)\) appears \(t\)-apart in exactly one block of \(B\) and no ordered pair \((a, b) \in Y \times Y\) appears in any block of \(B\) for any \(t\), where \(1 \leq t \leq k – 1\). In this paper, some basic necessary conditions for the existence of a \(k\)-IMPD\((v, n)\) are easily obtained, namely,
\((v – n)(v – (k – 1)n – 1) \equiv 0 \pmod{k} \quad {and} \quad v > (k – 1)n + 1.\) It is shown that these basic necessary conditions are also sufficient for the case \(k = 3\), with the one exception of \(v = 6\) and \(n = 1\). Some problems relating to embeddings of perfect Mendelsohn designs and associated quasigroups are mentioned.

The fact that any \(n\)-vertex \(4\)-connected maximal planar graph admits at least \(\frac{3n+6}{5}\) \(4\)-contractible edges readily follows from the general results of W.D. McCuaig [9], [10] ,[11] and of L. Andersen, H. Fleischner, and B. Jackson [1].

Here we prove a lower bound of \(\lceil\frac{3n}{4}\rceil\) on the number of \(4\)-contractible edges in every \(4\)-connected maximal planar graph with at least eight vertices.

The problem of fairly dividing a piece of cake apparently originates with Hugo Steinhaus in 1948 at which time he raised the question of the number of cuts required in fair division algorithms. In this paper, an algorithm requiring \(O(n\log n)\) cuts is given, improving known algorithms which require \(O(n^2)\) or more cuts. The algorithm is shown to be optimal in a certain class, and general algorithms are shown to allow a certain freedom of participants to choose pieces.

We study the lattice generated by the class of \(m\) by \(n\) matrices of \(0\)’s and \(1\)’s with a fixed row sum vector and a fixed column sum vector.

In this paper, we study a problem related to one of the Turán problems: What is the maximum number of edges in a 3-graph without a complete subgraph on five vertices, the \(K_5\)? We prove that the exact bound Turan conjectured is true if we forbid a larger class of subgraphs including \(K_5\).

If \(f\) and \(g\) are self-maps on a finite set \(M\) with \(n = |M|\), then the images of various composite functions such as \(f^2gf\) and \(g^2 f^2 g\) may have different sizes. There is, of course, a minimal image size which can be achieved by the composition of particular functions. It can be difficult, however, to discover the size of this minimal image. We seek to determine “words” over a finite alphabet \(S \) which, by specifying function compositions when letters are interpreted as functions, allow one to test for each \(k\) whether or not there exists among all compositions an image of size \(n – k\) or less. For two functions \(f\) and \(g\), \(W_1 = fg\) is clearly such a “word” for \(k = 1\), since no composition of functions \(f\) and \(g\) has an image smaller than or equal to \(|M| – 1\), if \(W_1 = fg\) fails to do so. We prove the existence of such a word \(W_k\) for each \(k\), and exhibit a recursive procedure for the generation of \(W_{k+1}\) from \(W_k\). The words \(W_k\) depend only upon the finite alphabet \( S \), and are independent of the size of the finite set \(M\) over which the symbols from \( S \) are to be interpreted as functions.

It is shown that a symmetric design with \(\lambda=2\) can admit \(PSL(2,q)\) for \(q\) odd and \(q\) greater than \(3\) as an automorphism group fixing a block and acting in its usual permutation representation on the points of the block only if \(q\) is congruent to \(5\pmod{8}\). A consequence for more general automorphism groups is also described.