Let \(S\) be a simple polygon in the plane whose vertices may be partitioned into sets \(A’, B’\), such that for every two points of \(A’\) (of \(B’\)), the corresponding segment is in \(S\). Then \(S\) is a union of \(6\) (or possibly fewer) convex sets. The number \(6\) is best possible. Moreover, the simple connectedness requirement for set \(S\) cannot be removed.

An \(\lambda\)-design on \(v\) points is a set of \(v\) distinct subsets (blocks) of a \(v\)-element set (points) such that any two different blocks meet in exactly \(\lambda\) points and not all of the blocks have the same size. Ryser’s and Woodall’s \(\lambda\)-design conjecture states that all \(\lambda\)-designs can be obtained from symmetric designs by a certain complementation procedure. The main result of the present paper is that the \(\lambda\)-design conjecture is true when \(v = 8p + 1\), where \(p \equiv 1\) or \(7\) (mod \(8\)) is a prime number.

For an ordered set \(W = \{w_1, w_2, \ldots, w_e\}\) of vertices and a vertex \(v\) in a connected graph \(G\), the representation of \(v\) with respect to \(W\) is the \(e\)-vector \(r(v|W) = (d(v, w_1), d(v, w_2), \ldots, d(v, w_k))\), where \(d(x, y)\) represents the distance between the vertices \(x\) and \(y\). The set \(W\) is a resolving set for \(G\) if distinct vertices of \(G\) have distinct representations with respect to \(W\). A resolving set for \(G\) containing a minimum number of vertices is a basis for \(G\). The dimension \(\dim(G)\) is the number of vertices in a basis for \(G\). A resolving set \(W\) of \(G\) is connected if the subgraph \(\langle W \rangle\) induced by \(W\) is a connected subgraph of \(G\). The minimum cardinality of a connected resolving set in a graph \(G\) is its connected resolving number \(cr(G)\). The relationship between bases and minimum connected resolving sets in a graph is studied. A connected resolving set \(W\) of \(G\) is a minimal connected resolving set if no proper subset of \(W\) is a connected resolving set. The maximum cardinality of a minimal connected resolving set is the upper connected resolving number \(cr^+(G)\). The upper connected resolving numbers of some well-known graphs are determined. We present a characterization of nontrivial connected graphs of order \(n\) with upper connected resolving number \(n-1\). It is shown that for a pair \(a,b\) of integers with \(1 \leq a \leq b\) there exists a connected graph \(G\) with \(cr(G) = a\) and \(cr^+(G) = b\) if and only if \((a,b) \neq (1,4)\) for all \(i > 2\).

We give six improved bounds on \(A(n,d,w)\), the maximum cardinality of a binary code of length \(n\) with minimum distance \(d\) and constant weight \(w\).

In this paper, we show that if \(G\) is an “\(\alpha\)-labeled” graph and if \(H\) is a “pseudograceful” graph, then \(G \cup H\) can be graceful or “pseudograceful” under some conditions on the \(\alpha\)-labeling function of \(G\). This generalizes Theorem 2.1 of [21]. We also show that if \(G\) is a Skolem-graceful, then \(G + \overline{K_n}\) is graceful for all \(n \geq 1\). We also give a partial answer to the question in [1] about the gracefulness of \(\overline{K_n} + mK_2\) for \(m \geq 3\). Finally, we complete the characterization of graceful graphs in the family \(C_m \cup S_n\).

We study the discrete version of the \(p\)-Laplacian operator — \(\textrm{div}(|\nabla u|^{p-2}\nabla u)\) — and we give some estimates of its smallest positive eigenvalue. In earlier papers, eigenvalues of the discrete Laplacian have been considered. We shall here study more general means. We shall also, in particular, study the case when the graph is complete. We give an estimate of the smallest positive eigenvalue of the \(p\)-Laplacian when the graph is a subgraph of \(\mathbb{Z}^n\) in this context. We give all eigenvalues of the \(p\)-Laplacian when the graph is complete.

Bipartite permutation graphs have several nice characterizations in terms of vertex ordering. Besides, as AT-free graphs, they have a linear structure in the sense that any connected bipartite permutation graph has a dominating path. In the present paper, we elaborate the linear structure of bipartite permutation graphs by showing that any connected graph in the class can be stretched into a “path” with “edges” being chain graphs. A particular consequence from the obtained characterization is that the clique-width of bipartite permutation graphs is unbounded, which refines a recent result of Golumbic and Rotics for permutation graphs.

A known result due to Matthews and Sunner is that every \(2\)-connected claw-free graph on \(n\) vertices contains a cycle of length at least \(\min\{2\delta+4,n\}\), and is Hamiltonian if \(n \leq 3\delta+2\). In this paper, we show that every \(2\)-connected claw-free graph on \(n\) vertices which does not belong to one of three classes of exceptional graphs contains a cycle of length at least \(\min\{4\delta-2,n\}\), hereby generalizing several known results. Moreover, the bound \(4\delta-2\) is almost best possible.

A graph or a digraph \(G\) is called super-edge-connected or super-\(\lambda\), if every minimum edge cut consists of edges adjacent to or from a vertex of minimum degree. Clearly, if \(G\) is super-\(\lambda\), then \(\lambda(G) = \delta(G)\), where \(\delta(G)\) is the minimum degree and \(\lambda(G)\) is the edge-connectivity of \(G\).

In this paper, degree sequence conditions for graphs and digraphs as well as for bipartite graphs and digraphs to be super-\(\lambda\) are presented.

Given integers \(k \geq 2\) and \(n \geq k\), let \(e(n, k)\) denote the maximum possible number of edges in an \(m\)-vertex graph which has no \(k\)-connected subgraph. It is immediate that \(e(n, 2) = n – 1\). Mader [2] conjectured that for every \(k \leq 2\), if \(n\) is sufficiently large then \(c(n, k) \leq (1.5k-2)(n – k + 1),\) where equality holds whenever \(k – 1\) divides \(n\). In this note we prove that when \(n\) is sufficiently large then \(e(n, k) \leq \frac{193}{120}(k – 1)(n – k + 1) < 1.61(k – 1)(n – k + 1),\) thereby coming rather close to the conjectured bound.