The clique operator \(K\) maps a graph \(G\) into its clique graph, which is the intersection graph of the (maximal) cliques of \(G\). Recognizing clique graphs is a problem known to be in NP, but no polynomial time algorithm or proof of NP-completeness is known. In this note we prove that this recognition problem can be reduced to the case of graphs of diameter at most two.

The skewness of a graph \(G\) is the minimum number of edges that need to be deleted from \(G\) to produce a planar graph. The splitting number of a graph \(G\) is the minimum number of splitting steps needed to turn \(G\) into a planar graph; where each step replaces some of the edges \(\{u,v\}\) incident to a selected vertex \(u\) by edges \(\{u’,v\}\), where \(u’\) is a new vertex. We show that the splitting number of the toroidal grid graph \(C_n \times C_m\) is \(\min\{n,m\} – 2\delta_{n,3}\delta_{m,3} – \delta_{n,4}\delta_{m,3} – \delta_{n,3}\delta_{m,4}\) and its skewness is \(\min\{n, m\} – \delta_{n,3}\delta_{m,3 }- \delta_{n,4}\delta_{m,3} – \delta_{n,3}\delta_{m,4}\). Here, \(\delta\) is the Kronecker symbol, i.e., \(\delta_{i,j}\) is \(1\) if \(i = j\), and \(0\) if \(i \neq j\).

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\).