The study of the maximum size \(ex(n; K_{t,t})\) of a graph of order \(n\) not containing the complete bipartite graph \(K_{t,t}\) as a subgraph is the aim of this paper. We show an upper bound for this extremal function that is optimum for infinitely many values of \(n\) and \(t\). Moreover, we characterize the corresponding family of extremal graphs.

In this paper we extend the work of Bogart and Trenk [3] and Fishburn and Trotter [6] in studying different classes of bitolerance orders. We provide a more comprehensive list of classes of bitolerance orders and prove equality between some of these classes in general and other classes in the bipartite domain. We also provide separating examples between unequal classes of bitolerance orders.

We consider non-crossing trees and show that the height of node \(\rho n\) with \(0 < p < 1\) in a non-crossing tree of size \(n\) is asymptotically Maxwell-distributed. We also give an asymptotic formula for the expected height of node \(\rho n\).

Let \(G = (V(G), E(G))\) be a finite simple graph with \(p\) vertices and \(n\) edges. A labeling of \(G\) is an injection \(f: V(G) \to {Z}_n\). A labeling of \(G\) is called \(2\)-sequential if \(f(V(G)) = \{r, r+1, \ldots, r+p-1\}\) (\(0 \leq r <r+ p-1 \leq n-1\)) and the induced edge labeling \(f^*: E(G) \to \{0, 1, \ldots, n-1\}\) given by \[f^*(u,v) = f(u) + f(v), \quad \text{for every edge } (u,v) \] forms a sequence of distinct consecutive integers \(\{k, k+1, \ldots, n+k-1\}\) for some \(k\) (\(1 \leq k \leq n-2\)). By utilizing the graphs having \(2\)-sequential labeling, several new families of sequential graphs are presented.

A cycle \(C\) in a graph \(G\) is said to be a dominating cycle if every vertex of \(G\) has a neighbor on \(C\). Strengthening a result of Bondy and Fan [3] for tough graphs, we prove that a \(k\)-connected graph \(G\) (\(k \geq 2\)) of order \(p\) with \(t(G) > \frac{k}{k+1}\) has a dominating cycle if \(\sum_{x \in S} \geq p – 2k – 2\) for each \(S \subset V(G)\) of order \(k+1\) in which every pair of vertices in \(S\) have distance at least four in \(G\).

Let \(G = (V,E)\) be an n-vertex graph and \(f : V \rightarrow \{1,2,\ldots,n\}\) be a bijection. The additive bandwidth of \(G\), denoted \(B^+(G)\), is given by \(B^+(G) = \min_{f} \max_{u,v\in E} |f(u) + f(v) – (n+1)|\), where the minimum ranges over all possible bijections \(f\). The additive bandwidth cannot decrease when an edge is added, but it can increase to a value which is as much as three times the original additive bandwidth. The actual increase depends on \(B^+(G)\) and n and is completely determined.

In Minimal Enclosings of Triple Systems I, we solved the problem of minimal enclosings of \(\text{BIBD}(v, 3, \lambda)\) into \(\text{BIBD}(v+1, 3, \lambda+m)\) for \(1 \leq \lambda \leq 6\) with a minimal \(m \geq 1\). Here we consider a new problem relating to the existence of enclosings for triple systems for any \(v\), with \(1 < 4 < 6\), of \(\text{BIBD}(v, 3, \lambda)\) into \(\text{BIBD}(v+s, 3, \lambda+1)\) for minimal positive \(s\). The non-existence of enclosings for otherwise suitable parameters is proved, and for the first time the difficult cases for even \(\lambda\) are considered. We completely solve the case for \(\lambda \leq 3\) and \(\lambda = 5\), and partially complete the cases \(\lambda = 4\) and \(\lambda = 6\). In some cases a \(1\)-factorization of a complete graph or complete \(n\)-partite graph is used to obtain the minimal enclosing. A list of open cases for \(\lambda = 4\) and \(\lambda = 6\) is attached.

Halin’s Theorem characterizes those locally finite infinite graphs that embed in the plane without accumulation points by giving a set of six topologically-excluded subgraphs. We prove the analogous theorem for graphs that embed in an open Möbius strip without accumulation points. There are \(153\) such obstructions under the ray ordering defined herein. There are \(350\) obstructions under the minor ordering. There are \(1225\) obstructions under the topological ordering. The relationship between these graphs and the obstructions to embedding in the projective plane is similar to the relationship between Halin’s graphs and \(\{K_5, K_{3,3}\}.^1\)

In [5] Pila presented best possible sufficient conditions for a regular \(\sigma\)-connected graph to have a \(1\)-factor, extending a result of Wallis [7]. Here we present best possible sufficient conditions for a \(\sigma\)-connected regular graph to have a \(k\)-factor for any \(k \geq 2\).