The vertices \(V\) of trees with maximum degree three and \(t\) degree two vertices are partitioned into sets \(R\), \(B\), and \(U\) such that the induced subgraphs \(\langle V – R \rangle\) and \(\langle V – B \rangle\) are isomorphic and \(|U|\) is minimum. It is shown for \(t \geq 2\) that there is such a partition for which \(|U| = 0\) if \(t\) is even and \(|U| = 1\) if \(t\) is odd. This extends earlier work by the authors which answered this problem when \(t = 0\) or \(1\).

Let G be a simple connected graph on 2n vertices with a perfect matching. For a positive integer k, \(1 \leq \text{k} \leq \text{n}-1\), G is \(k\)-extendable if for every matching M of size k in G, there is a perfect matching in G containing all the edges of M. For an integer k, \(0 \leq \text{k} \leq \text{n} – 2\), G is trongly \(k\)-extendable if \(\text{G} – \{\text{u, v}\}\) is \(k\)-extendable for every pair of vertices u and v of G. The problem that arises is that of characterizing k-extendable graphs and strongly k-extendable graphs. The first of these problems has been considered by several authors while the latter has been recently investigated. In this paper, we focus on a minimum cutset of strongly k-extendable graphs. For a minimum cutset S of a strongly k-extendable graph G, we establish that if \(|\text{S}| = \text{k + t}\), for an integer \(\text{t} \geq 3\), then the independence number of the induced subgraph G[S] is at most \(2\) or at least k + 5 – t. Further, we present an upper bound on the number of components of G – S.

Let \(\{G_{pn} | n \geq 1\} = \{G_{p1}, G_{p2}, G_{p3}, \ldots\}\) be a countable sequence of simple graphs, where \(G_{pn}\) has \(pn\) vertices. This sequence is called \(K_p\)-removable if \(G_{p1} = K_p\), and \(G_{pn} – K_p = G_{p(n-1)}\) for every \(n \geq 2\) and for every \(K_p\) in \(G_{pn}\). We give a general construction of such sequences. We specialize to sequences in which each \(G_{pn}\) is regular; these are called regular \((K_p, \lambda)\)-removable sequences, where \(\lambda\) is a fixed number, \(0 \leq \lambda \leq p\), referring to the fact that \(G_{pn}\) is \((\lambda(n – 1) + p – 1)\)-regular. We classify regular \((K_p, 0)\)-, \((K_p, p – 1)\)-, and \((K_p, p)\)-removable sequences as the sequences \(\{nK_p | n \geq 1\}\), \(\{K_{p \times n} | n \geq 1\}\), and \(\{K_{pn} | n \geq 1\}\) respectively. Regular sequences are also constructed using `levelled’ Cayley graphs, based on a finite group. Some examples are given.

A graph \(G\) is called an \(L_1\)-graph if, for each triple of vertices \(u, v,\) and \(w\) with \(d(u,v) = 2\) and \(w \in N(u) \cap N(v)\), \(d(u) + d(v) \geq |N(u) \cup N(v) \cup N(w)| – 1\). Let \(G\) be a 2-connected \(L_1\)-graph of order \(n\). If \(\sigma_3(G) \geq n – 2\), then \(G\) is hamiltonian or \(G \in \mathcal{K}\), where \(\sigma_3(G) = \min\{d(u) + d(v) + d(w) : \{u,v,w\} \text{ is an independent set in } G\}\), \(\mathcal{K}=\{G: K_{p, p+1} \subseteq G \subseteq K_p + (p+1)K_1 for some p \geq 2\}\). A similar result on the traceability of connected \(L_1\)-graphs is also obtained.

For a graph \(G\), the jump graph \(J(G)\) is that graph whose vertices are the edges of \(G\) and where two vertices of \(J(G)\) are adjacent if the corresponding edges are not adjacent. For \(k \geq 2\), the \(k\)th iterated jump graph \(J^k(G)\) is defined as \(J(J^{k-1}(G))\), where \(J^1(G) = J(G)\). An infinite sequence \(\{G_i\}\) of graphs is planar if every graph \(G_i\) is planar; while the sequence \(\{G_i\}\) is nonplanar otherwise. All connected graphs \(G\) for which \(\{J^k(G)\}\) is planar have been determined. In this paper, we investigate those connected graphs \(G\) for which \(\{J^k(G)\}\) is nonplanar. It is shown that if \(\{J^k(G)\}\) is a nonplanar sequence, then \(J^k(G)\) is nonplanar for all \(k \geq 4\). Furthermore, there are only six connected graphs \(G\) for which \(\{J^k(G)\}\) is nonplanar and \(J^3(G)\) is planar.

We examine a query posed as a conjecture by Key and Moori [11, Section 7] concerning the full automorphism groups of designs and codes arising from primitive permutation representations of finite simple groups, and based on results for the Janko groups \(J_1\) and \(J_2\) as studied in [11]. Here, following that same method of construction, we show that counter-examples to the conjecture exist amongst some representations of some alternating groups, and that the simple symplectic groups in their natural representation provide an infinite class of counter-examples.

In this paper, we show that for every sufficiently large integer \(n\) and every positive integer \(c \leq \left\lfloor \frac{1}{6}({\log \log n})^\frac{1}{2} \right \rfloor\), a Boolean lattice with \(n\) atoms can be partitioned into chains of cardinality \(c\), except for at most \(c-1\) elements which also form a chain.

We construct all self-dual \([24, 12, 8]\) quaternary codes with a monomial automorphism of prime order \(r > 3\) and obtain a unique code for \(r = 23\) (which has automorphisms of orders \(5\), \(7\), and \(11\) too), two inequivalent codes for \(r = 11\), \(6\) inequivalent codes for \(r = 7\), and \(12\) inequivalent codes for \(r = 5\). The obtained codes have \(12\) different weight spectra.

Metamorphoses of small \(k\)-wheel systems for \(k = 3, 4,\) and \(6\) are obtained. In particular, we obtain simultaneous metamorphoses of: \(3\)-wheel systems into Steiner triple systems and into \(K_{1,3}\)-designs; \(4\)-wheel systems into \(4\)-cycle systems, \(K_{1,4}\)-designs, and bowtie systems; \(6\)-wheel systems into \(6\)-cycle systems, \(K_{1,6}\)-designs, and \(3\)-windmill designs or near-\(3\)-windmill designs.

We deal with the problem of labeling the vertices, edges, and faces of a plane graph in such a way that the label of a face and the labels of the vertices and edges surrounding that face add up to a weight of that face, and the weights of all the faces constitute an arithmetical progression of difference \(d\).