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

The notion of fusion in association schemes is developed and then applied to group schemes. It is shown that the association schemes derived in [1] and [4] are special cases of \(A\)-fused schemes of group schemes \(X(G)\), where \(G\) is abelian and \(A\) is a group of automorphisms of \(G\). It is then shown that these latter schemes give rise to PBIB designs under constructions identical to those found in [1] and [4].

Let \(G = (X, E)\) be any graph. Then \(D \subset X\) is called a dominating set of \(G\) if for every vertex \(x \in X – D\), \(x\) is adjacent to at least one vertex of \(D\). The domination number, \(\gamma(G)\), is \(\min \{|D| \mid D\) { is a dominating set of } \(G\}\). In 1965 Vizing gave the following conjecture: For any two graphs \(G\) and \(H\)

\[\gamma(G \times H) \geq \gamma(G) . \gamma(H).\]

In this paper, it is proved that \(\gamma(G \times H) > \gamma(G) . \gamma(H)\) if \(H\) is either one of the following graphs: (a) \(H = G^-\), i.e., complementary graph of \(G\), (b) \(H = C_m\), i.e., a cycle of length \(m\) or (c) \(\gamma(H) \leq 2\).

In [1],[2], there are many assignment models. This paper gives a new assignment model and an algorithm for solving this problem.

Let \(v, k\), and \(n\) be positive integers. An incomplete perfect Mendelsohn design, denoted by \(k\)-IMPD\((v, n)\), is a triple \((X, Y, B)\) where \(S\) is a \(v\)-set (of points), \(Y\) is an \(n\)-subset of \(X\), and \(B\) is a collection of cyclically ordered \(k\)-subsets of \(X\) (called blocks) such that every ordered pair \((a, b) \in (X \times X) \setminus (Y \times Y)\) appears \(t\)-apart in exactly one block of \(B\) and no ordered pair \((a, b) \in Y \times Y\) appears in any block of \(B\) for any \(t\), where \(1 \leq t \leq k – 1\). In this paper, some basic necessary conditions for the existence of a \(k\)-IMPD\((v, n)\) are easily obtained, namely,
\((v – n)(v – (k – 1)n – 1) \equiv 0 \pmod{k} \quad {and} \quad v > (k – 1)n + 1.\) It is shown that these basic necessary conditions are also sufficient for the case \(k = 3\), with the one exception of \(v = 6\) and \(n = 1\). Some problems relating to embeddings of perfect Mendelsohn designs and associated quasigroups are mentioned.

The fact that any \(n\)-vertex \(4\)-connected maximal planar graph admits at least \(\frac{3n+6}{5}\) \(4\)-contractible edges readily follows from the general results of W.D. McCuaig [9], [10] ,[11] and of L. Andersen, H. Fleischner, and B. Jackson [1].

Here we prove a lower bound of \(\lceil\frac{3n}{4}\rceil\) on the number of \(4\)-contractible edges in every \(4\)-connected maximal planar graph with at least eight vertices.

The problem of fairly dividing a piece of cake apparently originates with Hugo Steinhaus in 1948 at which time he raised the question of the number of cuts required in fair division algorithms. In this paper, an algorithm requiring \(O(n\log n)\) cuts is given, improving known algorithms which require \(O(n^2)\) or more cuts. The algorithm is shown to be optimal in a certain class, and general algorithms are shown to allow a certain freedom of participants to choose pieces.

We study the lattice generated by the class of \(m\) by \(n\) matrices of \(0\)’s and \(1\)’s with a fixed row sum vector and a fixed column sum vector.

In this paper, we study a problem related to one of the Turán problems: What is the maximum number of edges in a 3-graph without a complete subgraph on five vertices, the \(K_5\)? We prove that the exact bound Turan conjectured is true if we forbid a larger class of subgraphs including \(K_5\).

If \(f\) and \(g\) are self-maps on a finite set \(M\) with \(n = |M|\), then the images of various composite functions such as \(f^2gf\) and \(g^2 f^2 g\) may have different sizes. There is, of course, a minimal image size which can be achieved by the composition of particular functions. It can be difficult, however, to discover the size of this minimal image. We seek to determine “words” over a finite alphabet \(S \) which, by specifying function compositions when letters are interpreted as functions, allow one to test for each \(k\) whether or not there exists among all compositions an image of size \(n – k\) or less. For two functions \(f\) and \(g\), \(W_1 = fg\) is clearly such a “word” for \(k = 1\), since no composition of functions \(f\) and \(g\) has an image smaller than or equal to \(|M| – 1\), if \(W_1 = fg\) fails to do so. We prove the existence of such a word \(W_k\) for each \(k\), and exhibit a recursive procedure for the generation of \(W_{k+1}\) from \(W_k\). The words \(W_k\) depend only upon the finite alphabet \( S \), and are independent of the size of the finite set \(M\) over which the symbols from \( S \) are to be interpreted as functions.

It is shown that a symmetric design with \(\lambda=2\) can admit \(PSL(2,q)\) for \(q\) odd and \(q\) greater than \(3\) as an automorphism group fixing a block and acting in its usual permutation representation on the points of the block only if \(q\) is congruent to \(5\pmod{8}\). A consequence for more general automorphism groups is also described.

In this paper, we consider the structure of \(k\)-saturated graphs \((G \not\supset K_k,\) but \(G+e \supset K_{k}\) for all possible edges \(e)\\) having chromatic number at least \(k\).

In this paper, the authors study the vulnerability parameters of integrity, toughness, and binding number for two classes of graphs. These two classes of graphs are permutation graphs of complete graphs and permutation graphs of complete bipartite graphs

In this paper we examine bounds on \(|N(x) \cup N(y)|\) (for nonadjacent pairs \(x,y \in V(G)\)) that imply certain strong Hamiltonian properties in graphs. In particular, we show that if \(G\) is a 2-connected graph of order \(n\) and if for all pairs of distinct nonadjacent vertices \(x, y \in V(G)\),

1. \(|N(z) \cup N(y)| \geq \frac{2n+5}{3}\), then \(G\) is pancyclic.
2. \(|N(z) \cup N(y)| \geq n-t\) and \(\delta(G) \geq t\), then \(G\) is Hamiltonian.
3. \(|N(z) \cup N(y)| \geq n-2\), then \(G\) is vertex pancyclic.

Three types of graphs are investigated with respect to cordiality, namely:graphs which are the complete product of two cordial graphs, graphs which are the subdivision graphs of cordial graphs, cactus graphs.
We give sufficient conditions for the cordiality of graphs of the first two types and show that a cactus graph is cordial if and only if the cardinality of its edge set is not congruent to \(2\) (mod 4).

It is shown that there exists a 4-critical 3-uniform linear hypergraph of order \(m\) for every \(m \geq 56\).

Essentially all pairs of forests \((F_1,F_2)\) are determined for which \(R(F_1,F_2)\) is finite, where \(R(F_1,F_2)\) is the class of minimal Ramsey graphs for the pair \((F_1,F_2)\).

Steiner Heptagon Systems (SHS) of type 1, 2, and 3 are defined and the spectrum of type 2 SHSs (SHS2) is studied. It is shown that the condition \(n \equiv 1 \) { or } \(7 \pmod{14}\) is not only necessary but also sufficient for the existence of an SHS2 of order \(n\), with the possible exceptions of \(n=21\) and \(85\). This gives an interesting algebraic result since the study of SHS2s is equivalent to the study of quasigroups satisfying the identities \(x^2 = x\), \((yx)x = y\), and \((xy)(y(xy)) = (yx)(x(yx))\).

A graph is called well-covered if every maximal independent set has the same size. One generalization of independent sets in graphs is that of a fractional cover – attach nonnegative weights to the vertices and require that for every vertex the sum of all the weights in its closed neighbourhood be at least 1. In this paper, we consider and characterize fractionally well-covered graphs.

We prove that \(e(3,k+1,n) \geq 6n-13k\), where \(e(3,k+1,n)\) is the minimum number of edges in any triangle-free graph on \(n\) vertices with no independent set of size \(k+1\). To achieve this, we first characterize all such graphs with exactly \(e(3,k+1,n)\) edges for \(n \leq 3k\). These results yield some sharp lower bounds for the independence ratio for triangle-free graphs. In particular, the exact value of the minimal independence ratio for graphs with average degree \(4\) is shown to be \(\frac{4}{13}\). A slight improvement to the general upper bound for the classical Ramsey \(R(3,k)\) numbers is also obtained.

In this paper, we prove that for any \(n > 27363\), \(n \equiv 3\) modulo {6}, there exist a pair of orthogonal Steiner triple systems of order \(n\). Further, a pair of orthogonal Steiner triple systems of order \(n\) exist for all \(n \equiv 3\) modulo {6}, {3} \(< n \leq 27363\), with at most \(918\) possible exceptions. The proof of this result depends mainly on the construction of pairwise balanced designs having block sizes that are prime powers congruent to \(1\) modulo {6}, or \(15\) or \(27\). Some new examples are also constructed recursively by using conjugate orthogonal quasigroups.

We give a bijective proof for the identity \(S(n,k) \equiv \binom{n-j-1}{n-k} \pmod{2}\)
where \(j = \lfloor \frac{k}{2} \rfloor\) is the largest integer \(\leq\frac{k}{2}\) .

A bicover of pairs by quintuples of a \(v\)-set \(V\) is a family of 5-subsets of \(V\) (called blocks) with the property that every pair of distinct elements from \(V\) occurs in at least two blocks. If no other such bicover has fewer blocks, the bicover is said to be minimum, and the number of blocks in a minimum bicover is the covering number \(C_2(v, 5, 2)\), or simply \(C_2(v)\). It is well known that \(C_2(v) \geq \left \lceil \frac{v\left \lceil{(v-1)/2}\right \rceil}{5} \right \rceil = B_2(v)\), where \(\lceil x \rceil\) is the least integer not less than \(x\). It is shown here that if \(v\) is odd and \(v\not\equiv 3\) mod 10, \(v\not=9\) or 15,then \(C_2(v)=B(v)\).