Suppose \(\Gamma\) is a finite multiplicative group and \(S \subseteq \Gamma\) satisfies \(1 \notin S\) and \(S^{-1} = \{x^{-1} | x \in S\} = S\). The abelian Cayley graph \(G = G(\Gamma, S)\) is the simple graph having vertex set \(V(G) = \Gamma\), an abelian group, and edge set \(E(G) = \{\{x, y\} | x^{-1}y \in S\}\). We prove the following regarding the chromatic index of an abelian Cayley graph \(G = G(\Gamma, S)\): if \(\langle S \rangle\) denotes the subgroup generated by \(S\), then \(\chi'(G) = \Delta(G)\) if and only if \(|\langle S \rangle|\) is even.

Let \(G\) be a graph and let \(D_1(G)\) denote the set of vertices of degree one in \(G\). In [1], Behocine, Clark, Kéhler, and Veldman conjectured that for a connected simple graph \(G\) of \(n\) vertices, if \(G – D_1(G)\) is \(2\)-edge-connected, and if for any edge \(xy \in E(G)\), \(d(x) + d(y) > \frac{2n}{5}-2\), then \(L(G)\) is hamiltonian.

In this note, we shall show that the conjecture above holds for a class of graphs that includes the \(K_{1,3}\)-free graphs, and we shall also characterize the extremal graphs.

A packing design (briefly packing) of order \(v\), block size \(k\), and index \(\lambda\) is a pair \((X,\mathcal{D})\) where \(X\) is a \(v\)-set (of points) and \(\mathcal{D}\) is a collection of \(k\)-subsets of \(X\) (called blocks) with cardinality \(b\) such that every \(2\)-subset of \(X\) is contained in at most \(\lambda\) blocks of \(\mathcal{D}\). We denote it by \(\mathrm{SD}(k,\lambda; v,b)\). If no other such packing has more blocks, the packing is said to be maximum, and the number of blocks in \(\mathcal{D}\) is the packing number \(\mathrm{D}(k,\lambda;v)\). For fixed \(k\),\(\lambda\) and \(v\), the packing problem is to determine the packing number. In this paper, the values of \(\mathrm{D}(5,2; v)\) are determined for all \(v \geq 5\) except \(48\) values of \(v\).

Behzad has conjectured that a simple graph G can always be totally coloured using two more colours than the maximum degree in G. The conjecture has been verified for several special classes of graphs by Behzad, Chartrand and Cooper, Rosenfeld,
and Meyer, and by Vijayaditya for graphs with maximum degree less than or equal to 3.We show algorithmically that the conjecture is true for graphs with maximum degree 4.

The concept of self-complementary (s.c.) graphs is extended to almost self-complementary graphs. We define an \(n\)-vertex graph to be almost self-complementary (a.s.c.) if it is isomorphic to its complement with respect to \(K_n – e\), the complete graph with one edge removed. A.s.c. graphs with \(n\) vertices exist if and only if \(n \equiv 2\) or \(3 \pmod{4}\), i.e., precisely when s.c. graphs do not exist. We investigate various properties of a.s.c. graphs.

A triangulation of a surface is \(\delta\)-regular if each vertex is contained in exactly \(\delta\) edges. For each \(\delta \geq 7\), \(\delta\)-regular triangulations of arbitrary non-compact surfaces of finite genus are constructed. It is also shown that for \(\delta \leq 6\) there is a \(\delta\)-regular triangulation of a non-compact surface \(\sum\) if and only if \(\delta = 6\) and \(\sum\) is homeomorphic to one of the following surfaces: the Euclidean plane, the two-way-infinite cylinder, or the open Möbius band.

The packing number \(D(2,k,v)\) is defined to be the maximum cardinality of a family of \(k\)-subsets, chosen from a set of \(v\) elements, such that no pair of elements appears in more than one \(k\)-subset. We examine \(D(2,k,v)\) for \(v < k(k-1)\) and determine such numbers for the case \(k=5\), \(v < 20\).

Ho and Shee [5] showed that for a graph \(G\) of order \(n\) \((\geq4)\) and size \(m\) to be cordial, it is necessary that \(m\) must be less than \(\frac{n(n-1)}{2} – \left\lceil\frac{n}{2}\right\rceil + 2\).

In this paper, we prove that there exists a cordial graph of order \(n\) and size \(m\), where
\(n-1\leq m\leq\frac{n(n-1)}{2} – \left\lceil\frac{n}{2}\right\rceil + 1.\)

Let \(B_n = K(1,1,n)\) denote the \(n\)-book. In this paper we (i) calculate \(\lambda(C_5, B_n)\) for all \(n\),
(ii) prove that if \(m\) is an odd integer \(\geq 7\) and \(n \geq 4m – 13\) then \(r(C_m, B_n) = 2n + 3\),and (iii)
prove that if \(m \geq 2n + 2\) then \(r(C_m, B_n) = 2m – 1\).