We introduce the notion of BP-spatial representation of a biconnected graph \(G = (V, E)\). We show that the spatiality degree of a BP-spatial representable graph is \(2(|E| – |V|)\). From this result, we derive the spatiality degree for planar and hamiltonian graphs.

We introduce the notion of premature partial Latin squares; these cannot be completed, but if any of the entries is deleted, a completion is possible. We study their spectrum, i.e., the set of integers \(t\) such that there exists a premature partial Latin square of order \(n\) with exactly \(t\) nonempty cells.

Given a digraph \(D\), its competition graph has the same vertex set and an edge between two vertices \(x\) and \(y\) if there is a vertex \(u\) so that \((x,u)\) and \((y,u)\) are arcs of \(D\). Motivated by a problem of communications, we study the competition graphs of the special digraphs known as semiorders. This leads us to define a condition on digraphs called \(C(p)\) and \(C^*(p)\) and to study the graphs arising as competition graphs of acyclic digraphs satisfying conditions \(C(p)\) or \(C^*(p)\).

A transversal cover is a set of \(gk\) points in \(k\) disjoint groups of size \(g\) and, ideally, a minimal collection of transversal subsets, called blocks, such that any pair of points not contained in the same group appears in at least one block. In this article we present a direct construction method for transversal covers using group divisible designs. We also investigate a particular infinite family of group divisible designs that yield particularly good covers.

For an ordered set \(A\) and \(B\) whose orders agree on its intersection, the gluing of \(A\) and \(B\) is defined to be the ordered set on the union of its underlying sets whose order is the transitive closure of the union of the orders of \(A\) and \(B\). The gluing number of an ordered set \(P\) is the minimum number of induced semichains (suborders of dimension at most two) of \(P\) whose consecutive gluing is \(P\). In this paper we investigate this parameter on some special ordered sets.

The aim of this paper is to give several characterizations for the following two classes of graphs: (i) graphs for which adding any \(l\) edges produces a graph which is decomposable into \(k\) spanning trees and (ii) graphs for which adding some \(l\) edges produces a graph which is decomposable into \(k\) spanning trees.

Upper and lower bounds are given for the toughness of generalized Petersen graphs. A lower bound of \(1\) is established for \(t(G(n,k))\) for all \(n\) and \(k\). This bound of \(1\) is shown to be sharp if \(n = 2k\) or if \(n\) is even and \(k\) is odd. The upper bounds depend on the parity of \(k\). For \(k\) odd, the upper bound \(\frac{n}{n-\frac{n+1}{2}}\) is established. For \(k\) even, the value \(\frac{2k}{2k-1}\) is shown to be an asymptotic upper bound. Computer verification shows the reasonableness of these bounds for small values of \(n\) and \(k\).

Suppose \(G\) is a graph. The minimum number of paths (trees, forests, linear forests, star forests, complete bipartite graphs, respectively) needed to decompose the edges of \(G\) is called the path number (tree number, arboricity, linear arboricity, star arboricity and biclique number, respectively) of \(G\). These numbers are denoted by \(p(G), t(G), a(G), la(G), sa(G), r(G)\), respectively. For integers \(1 \leq k \leq n\), let \(C_{n,k}\) be the graph with vertex set \(\{a_1,a_2,\ldots,a_n,b_1,b_2,\ldots,b_n\}\) and edge set \(\{a_ib_j :i=1,2,\ldots ,n,j \equiv i+1,i+2, \ldots ,i+k \text{(mod n)}\}\). We call \(C_{n,k}\) a crown. In this paper, we prove the following results:

1. \(p(C_{n,k}) = \begin{cases}
   n & \text{if \(k\) is odd}, \\
   {(\frac{k}{2})+1} & \text{if \(k\) is even}.
   \end{cases}\)
2. \(a(C_{n,k}) = t(C_{n,k}) = la(C_{n,k}) = \left\lceil \frac{k+1}{2} \right\rceil\) if \(k \geq 2\).
3. For \(k \geq 3\) and \(k \in \{3,5\} \cup \{n-3,n-2,n-1\}\),
   \[sa(C_{n,k}) = \begin{cases}
   \left\lceil \frac{k}{2} \right\rceil + 1 & \text{if \(k\) is odd}, \\
   \left\lceil \frac{k}{2} \right\rceil + 2 & \text{if \(k\) is even}.
   \end{cases}\]
4. \(r(C_{n,k}) = n\) if \(k \leq \frac{n+1}{2}\) or \(\gcd(k,n) = 1\).

Due to (3), (4), we propose the following conjectures.

\(\textbf{Conjecture A}\). For \(3 \leq k \leq n-1\),
\[sa(C_{n,k}) = \begin{cases}
\left\lceil \frac{k}{2} \right\rceil + 1 & \text{if \(k\) is odd}, \\
\left\lceil \frac{k}{2} \right\rceil + 2 & \text{if \(k\) is even}.
\end{cases}\]
\(\textbf{Conjecture B}\). For \(1 \leq k \leq n-1\), \(r(C_{n,k}) = n\).

Let \(G = (V, E)\) be a graph and \(A\) a non-trivial Abelian group, and let \(\mathcal{F}(G, A)\) denote the set of all functions \(f: E(G) \to A\). Denote by \(D\) an orientation of \(E(G)\). Then \(G\) is \(A\)-colorable if and only if for every \(f \in \mathcal{F}(G, A)\) there exists an \(A\)-coloring \(c: V(G) \to A\) such that for every \(e = (x,y) \in E(G)\) (assumed to be directed from \(x\) to \(y\)), \(c(x) – c(y) \neq f(e)\). If \(G\) is a graph, we define its group chromatic number \(\chi_1(G)\) to be the minimum number \(m\) for which \(G\) is \(A\)-colorable for any Abelian group \(A\) of order \(\geq m\) under the orientation \(D\). In this paper, we investigated the properties of the group chromatic number, proved the Brooks Type theorem for \(\chi_1(G)\), and characterized all bipartite graphs with group chromatic number at most \(3\), among other things.