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.

In this paper, we consider the structure of \(k\)-saturated graphs \((G \not\supset K_k,\) but \(G+e \supset K_{k}\) for all possible edges \(e)\\) having chromatic number at least \(k\).

In this paper, the authors study the vulnerability parameters of integrity, toughness, and binding number for two classes of graphs. These two classes of graphs are permutation graphs of complete graphs and permutation graphs of complete bipartite graphs

In this paper we examine bounds on \(|N(x) \cup N(y)|\) (for nonadjacent pairs \(x,y \in V(G)\)) that imply certain strong Hamiltonian properties in graphs. In particular, we show that if \(G\) is a 2-connected graph of order \(n\) and if for all pairs of distinct nonadjacent vertices \(x, y \in V(G)\),

1. \(|N(z) \cup N(y)| \geq \frac{2n+5}{3}\), then \(G\) is pancyclic.
2. \(|N(z) \cup N(y)| \geq n-t\) and \(\delta(G) \geq t\), then \(G\) is Hamiltonian.
3. \(|N(z) \cup N(y)| \geq n-2\), then \(G\) is vertex pancyclic.