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

For all nonnegative integers \(i,j\), let \(q(i, j)\) denote the number of all lattice paths in the plane from \((0,0)\) to \((i, j)\) with steps \((1,0)\), \((0,1)\), and \((1,1)\). In this paper, it is proved that

\[q(i_{n}p^{n}+…+i_0,j_np^n+…+j_0)\equiv(i_n,j_n)…q(i_0,j_0) \pmod{p}\]

where \(p\) is an odd prime and \(0 \leq i_k < p\), \(0 \leq j_k < p\). This relation implies a remarkable pattern to the divisibility of the array of numbers \(q(i, j)\).

Bauer and Tindell defined the graph invariant \(\wedge(G)\), for graphs \(G\) other than paths and the star \(K_{1,3}\), to be the least \(n\) for which \(G\) embeds in the \(n\)th iterated line graph of \(G\). They also proposed the problem of determining \(\wedge(T)\) for all trees \(T\). In this note, we completely solve this problem by showing that \(\wedge(T) = 3\) for any proper homeomorph \(T\) of \(K_{1,3}\) and that \(\wedge(T) = 2\) for all trees \(T\) which are neither paths nor homeomorphs of \(K_{1,3}\).

In a previous paper, all non-isomorphic decomposable \(3-(12,6,4)\) designs without repeated blocks were determined. These results are extended here by allowing repeated blocks. Under this condition, there are \(26\) non-isomorphic decomposable \(3-(12,6,4)\) designs, of which \(14\) have repeated blocks. Key blocks and point permutations for models of these designs are given, along with descriptions of their automorphism groups.

We extend the definition of edge-cordial graphs due to Ng and Lee for graphs on \(4k\), \(4k+1\), and \(4k+3\) vertices to include graphs on \(4k+2\) vertices, and show that, in fact, all graphs without isolated vertices are edge-cordial. Ng and Lee conjectured that all graphs on \(4k\), \(4k+1\), or \(4k+3\) vertices are edge-cordial.

We define the semibandwidth of a bipartite graph (whose bipartition is specified), which is a bipartite analogue of the bandwidth of a graph, and develop some of its properties. The motivation for this concept comes from the question of transforming a matrix by row and column permutations to as close to triangular form as possible.

Standard doubling and tripling constructions for block designs with block size three (triple systems) employ factorizations of complete graphs and of complete bipartite graphs. In these constructions, repeated edges in a factor lead to repeated blocks in the design. Hence the construction of triple systems with a prescribed number of repeated blocks is facilitated by determining the possible structure of repeated edges in the factors of a factorization of \(\lambda K_n\) and \(\lambda K_{n,n}\). For \(\lambda =3\), a complete determination of the possible combinations of numbers of doubly and triply repeated edges in 3-factorizations of \(\lambda K_n\) has been completed for \(n \geq12\). In this paper, we solve the analogous problem for the complete bipartite graphs in the case \(\lambda=3\). The case \(\lambda=1\) is trivial, and the case \(\lambda=2\) has been previously solved by Fu.

We obtain new base sequences, that is four sequences of lengths \(m + p\), \(m + p\), \(m\), \(m\), with \(p\) odd, which have zero auto correlation function which can be used with Yang numbers and four disjoint complementary sequences (and matrices) with zero non-periodic (periodic) auto correlation function to form longer sequences.

We give an alternate construction for \(T\)-sequences of length \((4n + 3)(2m + p)\), where \(n\) is the length of a Yang nice sequence.

These results are then used in the Goethals-Seidel or (Seberry) Wallis-Whiteman construction to determine eight possible decompositions into squares of \((4n + 3)(2m + p)\) in terms of the decomposition into squares of \(2m + 1\) when there are four suitable sequences of lengths \(m + 1\), \(m + 1\), \(m\), \(m\) and \(m\), the order of four Williamson type matrices. The new results thus obtained are tabulated giving \({OD}(4t; t, t, t, t)\) for the new orders \(t \in \{121, 135, 217, 221, 225, 231, 243, 245, 247,\\ 253, 255, 259, 261, 265, 273, 275, 279, 285, 287, 289, 295, 297, 299\}\).

The Hadamard matrix with greatest known excess for these new \(t\) is then listed.

We determine those pairs \((k,v)\), \(v = 4\cdot2^m, 5\cdot2^m\), for which there exists a pair of Steiner quadruple systems on the same \(v\)-set, such that the quadruples in one system containing a particular point are the same as those in the other system and moreover the two systems have exactly \(k\) other quadruples in common.

The point set “oval” has been considered in Steiner triple systems \((STS)\) and Steiner quadruple systems \((SQS)\) [3],[2]. There are many papers about “subsystems” in \(STS\) and \(SQS\). Generalizing and modifying the terms “oval” and “subsystem” we define the special point sets “near-oval” and “near-system” in Steiner quadruple systems. Considering some properties of these special point sets we specify how to construct \(SQS\) with near-ovals (\(S^{no}\)) and with near-systems (\(S^{ns}\)), respectively. For the same order of the starting system we obtain non-isomorphic systems \(S^{no}\) and \(S^{ns}\).

P. Paulraja recently showed that if every edge of a graph \(G\) lies in a cycle of length at most \(5\) and if \(G\) has no induced \(K_{i,s}\) as a subgraph, then \(G\) has a spanning closed trail. We use a weaker hypothesis to obtain a stronger conclusion. We also give a related sufficient condition for the existence of a closed trail in \(G\) that contains at least one end of each edge of \(G\).

Let \(G\) be a \(p\)-vertex graph which is rooted at \(x\). Informally, the rotation number \(h(G, x)\) is the smallest number of edges in a \(p\)-vertex graph \(F\) such that, for every vertex \(y\) of \(F\), there is a copy of \(G\) in \(F\) with \(x\) at \(y\). In this article, we consider rotation numbers for the generalized star graph consisting of \(k\) paths of length \(n\), all of which have a common endvertex, rooted at a vertex adjacent to the centre. In particular, if \(k = 3\) we determine the rotation numbers to within \(1, 2\) or \(3\) depending on the residue of \(n\) modulo \(6\).

The paper deals with combinatorial structures (pseudo-complexes, crystallizations) giving a direct link between the topology of triangulated manifolds and the theory of edge-coloured multigraphs. We define the concept of regular crystallization of a manifold and prove that every non-trivial handle-free closed \(n\)-manifold has a regular crystallization. Then we study some applications of regular crystallizations and give a counter-example to a conjecture of Y. Tsukui [20] about strong frames of the \(3\)-sphere.