A splitting partition for a graph \(G = (V, E)\) is a partition of \(V\) into sets \(R\), \(B\), and \(U\) so that the subgraphs induced by \(V – R\) and \(V – B\) are isomorphic. The splitting number \(\mu(G)\) is the size of \(|R|\) for any splitting partition which maximizes \(|R|\). This paper determines \(\mu(G)\) for trees of maximum degree at most three and exactly one degree two vertex and for trees all of whose vertices have degree three or one.

A decomposition of a digraph is said to be bicyclic if it admits an automorphism consisting of exactly two disjoint cycles. Necessary and sufficient conditions are given for the existence of bicyclic decompositions of the complete digraph into each of the four orientations of a 4-cycle.

The integrity of a graph \(G\), \(I(G)\), is defined by \(I(G) = min_{S \subseteq V(G)}\{|S| + m(G – S)\}\) where \(m(G – S)\) is the maximum order of the components of \(G – S\). In general, the integrity of an \(r\)-regular graph is not known [8]. We answer the following question for special regular graphs. For any given two integers \(p\) and \(r\) such that \(\frac{pr}{2}\) is an integer, is there an \(r\)-regular graph, say \(G^*\), on \(p\) vertices having size \(q = \frac{pr}{2}\) such that
\[I(G(p,\frac{pr}{2})) \leq I(G^*)\]
for all \(p\) and \(r\)? The \({integrity\; graph}\) is denoted by \(IG(p,n)\). It is a graph with \(p\) vertices, integrity \(n\), and has the least number of edges denoted by \(q[p,n]\). We compute \(q[p,n]\) for some values of \(p,n\).

If the distance between two vertices \(u\) and \(v\) in a graph \(G\) is \(k\), then \(u\) and \(v\) are said to \(k\)-step dominate each other. A set \(S\) of vertices of \(G\) is a \(k\)-step dominating set if every vertex of \(G\) is \(k\)-step dominated by some vertex of \(S\). The minimum cardinality of a \(k\)-step dominating set is the \(k\)-step domination number \(\rho_k(G)\) of \(G\). A sequence \(s: \ell_1, \ell_2, \ldots, \ell_k\) of positive integers is called an orbital dominating sequence for \(G\) if there exist distinct vertices \(v_1, v_2, \ldots, v_k\) of \(G\) such that every vertex of \(G\) is \(\ell_i\)-step dominated by \(v_i\) for some \(i\) (\(1 \leq i \leq k\)). An orbital dominating sequence \(s\) is minimal if no proper subsequence of \(s\) is an orbital dominating sequence for \(G\). The minimum length of a minimal orbital dominating sequence is the orbital domination number \(\gamma_{o}(G)\), while the maximum length of such a sequence is the upper orbital domination number \(\Gamma_{o}(G)\) of \(G\).

It is shown that for every pair \(i, j\) of positive integers with  \(i < j\), there exist graphs \(G\) and \(H\) such that both \(\rho_i(G) – \rho_j(G)\) and \(\rho_j(H) – \rho_i(H)\) are arbitrarily large. Also, there exist graphs \(G\) of arbitrarily large radius such that \(\gamma_{o}(G) < \rho_i(G)\) for every integer \(i\) (\(1 \leq i \leq \text{rad} G\)). All trees \(T\) with \(\gamma_{o}(T) = 3\) are characterized, as are all minimum orbital sequences of length 3 for graphs. All graphs \(G\) with \(\Gamma_{o}(G) = 2\) are characterized, as are all trees \(T\) with \(\Gamma_{o}(T) = 3\).

A Gray code is a list of words such that each word differs from its successor by a number of letters which is bounded independently of the length of the word. We use Roelants van Baronaigien’s I-code for involutions to derive a Gray code for all length-\(n\) involutions and one for those with a given number of length-2 cycles. In both Gray codes, each involution is transformed into its successor via one or two transpositions or a rotation of three elements. For both Gray codes we obtain algorithms for passing between a word and its position in the list and a non-recursive sequencing algorithm (transforming a given word into its successor or determining that it is the last word in the list) which runs in \(O(n)\) worst-case time and uses \(O(1)\) auxiliary variables; for involutions with a given number of length-2 cycles we also obtain a sequencing algorithm which runs in \(O(1)\) worst-case time and uses \(O(n)\) auxiliary variables. We generalize Chase’s method for obtaining non-recursive sequencing algorithms to any list of words in which all the words with a given suffix form an interval of consecutive words, and we show that if in addition the letter preceding the suffix always takes at least two distinct values in that interval, then Ehrlich’s method will find in \(O(1)\) time the rightmost letter in which a word differs from its successor.

An edge-colouring of a graph \(G\) is \({equitable}\) if, for each vertex \(v\) of \(G\), the number of edges of any one colour incident with \(v\) differs from the number of edges of any other colour incident with \(v\) by at most one. In the paper, we prove that any outerplanar graph has an equitable edge-colouring with \(k\) colours for any integer \(k \geq 3\).

In this paper we give alternative and shorter proofs of three theorems of Chetwynd and Hilton. All these three theorems have been widely used in many research papers.

The paper defines \((a, d)\)-face antimagic labeling of a certain class of convex polytopes. The possible values of \(d\) are determined as \(d = 2, 4\) or \(6\). For \(d = 2\) and \(4\) we produce \((9n + 3, 2)\) and \((6n + 4, 4)\)-face antimagic labelings for the polytopes.

The domination number \(\gamma(G)\) and the irredundance number \(ir(G)\) of a graph \(G\) have been considered by many authors. It is well known that \(ir(G) \leq \gamma(G)\) holds for all graphs \(G\). In this paper we determine all pairs of connected graphs \((X, Y)\) such that every graph \(G\) containing neither \(X\) nor \(Y\) as an induced subgraph satisfies \(ir(G) = \gamma(G)\).

We consider an inner product of a special type in the space of \(n\)-tuples over a finite field \({F}_q\), of characteristic \(p\). We prove that there is a very close relationship between the self-dual \(q\)-ary additive codes under this inner product and the self-dual \(p\)-ary codes under the usual dot product. We prove the MacWilliams identities for complete weight enumerators of \(q\)-ary additive codes with respect to the new inner product. We define a two-tuple weight enumerator of a binary self-dual code and prove that it is invariant of a group of order 384. We compute the Molien series of this group and find a good polynomial basis for the ring of its invariants.