Let \(R(n)\) denote the number of two-color partitions of \(n\). We obtain several identities concerning \(R(n)\).

We show that if \(M(n, m)\) denotes the time of a \((u, v)\)-minimum cut computation in a directed graph with \(n \geq 2\) nodes, \(m\) edges, and \(s\) and \(t\) are two distinct given nodes, then there exists an algorithm with \(O(n^2m+n\cdot M(n, m))\) running time for the directed minimum odd (or even) \((s, t)\)-cut problem and for its certain generalizations.

Basic properties of in-degree distribution of a general model of random digraphs \(D(n, \mathcal{P})\) are presented. Then some relations between random digraphs \(D(n, \mathcal{P})\) for different probability distributions \(\mathcal{P}\)’s are studied. In this context, a problem of the existence of a threshold function for every monotone digraph property of \(D(n, \mathcal{P})\) is discussed.

For a given structure (graph, multigraph, or pseudograph) \(G\) and an integer \(r \geq \Delta(G)\), a smallest inducing \(r\)-regularization of \(G\) (which is an \(r\)-regular superstructure of the smallest possible order, with bounded edge multiplicities, and containing \(G\) as an induced substructure) is constructed.

It is an established fact that some graph-theoretic extremal questions play an important part in the investigation of communication network vulnerability. Questions concerning the realizability of graph invariants are generalizations of these extremal problems. We define a \((p, q, \lambda, \delta)\) graph as a graph having \(p\) points, \(q\) lines, line connectivity \(\lambda\) and minimum degree \(\delta\). An arbitrary quadruple of integers \((a, b, c, d)\) is called \((p, q, \lambda, \delta)\) realizable if there is a \((p, q, \lambda, \delta)\) graph with \(p = a, q = b, \lambda = c\), and \(\delta = d\). Inequalities representing necessary and sufficient conditions for a quadruple to be \((p, q, \lambda, \delta)\) realizable are derived. In recent papers, the author gave necessary and sufficient conditions for \((p, q, \kappa, \Delta), (p, q, \lambda, \Delta), (p, q, \delta, \Delta)\) and \((p, q, \kappa, \delta)\) realizability, where \(\Delta\) denotes the maximum degree for all points in a graph and \(\lambda\) denotes the point connectivity of a graph. Boesch and Suffel gave the solutions for \((p, q, \kappa), (p, q, \lambda), (p, q, \delta), (p, \Delta, \delta, \lambda)\) and \((p, \Delta, \delta, \kappa)\) realizability in earlier manuscripts.

An aperiodic perfect map (APM) is an array with the property that each possible array of certain size, called a window, arises exactly once as a subarray in the array. In this article, we give some constructions which imply a complete answer for the existence of APMs with \(2 \times 2\) windows for any alphabet size.

A \(4\)-regular graph \(G\) is called a \(4\)-circulant if its adjacency matrix \(A(G)\) is a circulant matrix. Because of the special structure of the eigenvalues of \(A(G)\), the rank of such graphs is completely determined. We show how all disconnected \(4\)-circulants are made up of connected \(4\)-circulants and classify all connected \(4\)-circulants as isomorphic to one of two basic types.

Let \([n, k, d; g]\)-codes be linear codes of length \(n\), dimension \(k\) and minimum Hamming distance \(d\) over \(\mathrm{GF}(g)\). Let \(d_8(n, k)\) be the maximum possible minimum Hamming distance of a linear \([n, k, d; 8]\)-code for given values of \(n\) and \(k\). In this paper, twenty-two new linear codes over \(\mathrm{GF}(8)\) are constructed which improve the bounds on \(d_8(n, k)\).

We find new full orthogonal designs in order \(56\) and show that of
\(1285\) possible \(OD(56; s_1, s_2, s_3,56 – s_1 – s_2 – s_3)\) \(163\) are known, of
\(261\) possible \(OD(56; s_1, s_2, 56 – s_1 – s_2)\) \(179\) are known. All possible
\(OD(56; s_1,56 – s_1)\) are known.

Sattolo has presented an algorithm to generate cyclic permutations at random. In this note, the two parameters “number of moves” and “distance” are analyzed.

In this paper, we shall classify the self-complementary graphs with minimum degree exactly \(2\).

A graphical partition of the even integer \(n\) is a partition of \(n\) where each part of the partition is the degree of a vertex in a simple graph and the degree sum of the graph is \(n\). In this note, we consider the problem of enumerating a subset of these partitions, known as graphical forest partitions, graphical partitions whose parts are the degrees of the vertices of forests (disjoint unions of trees). We shall prove that

\[gf(2k) = p(0) + p(1) + p(2) + \cdots + p(k-1)\]

where \(g_f(2k)\) is the number of graphical forest partitions of \(2k\) and \(p(j)\) is the ordinary partition function which counts the number of integer partitions of \(j\).

We make further progress towards the forbidden-induced-subgraph characterization of the graphs with Hall number \(\leq 2\). We solve several problems posed in [4] and, in the process, describe all “partial wheel” graphs with Hall number \(\geq 2\) with every proper induced subgraph having Hall number \(\leq 2\).

A radio labeling of a connected graph $G$ is an assignment of distinct, positive integers to the vertices of \(G\), with \(x \in V(G)\) labeled \(c(x)\), such that

\[d(u, v) + |c(u) – c(v)| \geq 1 + diam(G)\]

for every two distinct vertices \(u,v\) of \(G\), where \(diam(G)\) is the diameter of \(G\). The radio number \(rn(c)\) of a radio labeling \(c\) of \(G\) is the maximum label assigned to a vertex of \(G\). The radio number \(rn(G)\) of \(G\) is \(\min\{rn(c)\}\) over all radio labelings \(c\) of \(G\). Radio numbers of cycles are discussed and upper and lower bounds are presented.

Dudeney’s round table problem was proposed about one hundred years ago. It is already solved when the number of people is even, but it is still unsettled except for only a few cases when the number of people is odd.

In this paper, a solution of Dudeney’s round table problem is given when \(n = p+2\), where \(p\) is an odd prime number such that \(2\) is the square of a primitive root of \(\mathrm{GF}(p)\), \(p \equiv 1 \pmod{4}\), and \(3\) is not a quadratic residue modulo \(p\).

In this paper, we characterize the potentially \(C_k\)-graphic sequence for \(k = 3, 4, 5\). These characterizations imply several theorems due to P. Erdős, M. S. Jacobson, and J. Lehel [1], R. J. Gould, M. S. Jacobson, and J. Lehel [2], and C. H. Lai [5] and [6], respectively.

Bailey, Cheng, and Kipnis [3] developed a method for constructing trend-free run orders of factorial experiments called the generalized fold-over method (GFM). In this paper, we use the GFM of constructing run orders of factorial experiments to give a systematic method of constructing magic squares of higher order.

In this paper, we focus on the identification of Latin interchanges in Latin squares that are the direct product of Latin squares of smaller orders. The results we obtain on Latin interchanges will be used to identify critical sets in direct products. This work is an extension of research carried out by Stinson and van Rees in \(1982\).

A \((g,k; \lambda)\)-difference matrix over the group \((G, o)\) of order \(g\) is a \(k\) by \(g\lambda\) matrix \(D = (d_{ij})\) with entries from \(G\) such that for each \(1 \leq i < j \leq k\), the multiset \(\{d_{il}\) o \(d_{jl}^{-1} \mid 1 \leq l \leq g\lambda\}\) contains every element of \(G\) exactly \(\lambda\) times. Some known results on the non-existence of generalized Hadamard matrices, i.e., \((g,g\lambda; \lambda)\)-difference matrices, are extended to \((g, g-1; \lambda)\)-difference matrices.

The notion of convexity in graphs is based on the one in topology: a set of vertices \(S\) is convex if an interval is entirely contained in \(S\) when its endpoints belong to \(S\). The order of the largest proper convex subset of a graph \(G\) is called the convexity number of the graph and is denoted \(con(G)\). A graph containing a convex subset of one order need not contain convex subsets of all smaller orders. If \(G\) has convex subsets of order \(m\) for all \(1 \leq m \leq con(G)\), then \(G\) is called polyconvex. In response to a question of Chartrand and Zhang [3], we show that, given any pair of integers \(n\) and \(k\) with \(2 \leq k < n\), there is a connected triangle-free polyconvex graph \(G\) of order \(n\) with convexity number \(k\).

In this work, \(\Gamma\) denotes a finite, simple, and connected graph. The \(k\)-excess \(e_k(H)\) of a set \(H \subseteq V(\Gamma)\) is defined as the cardinality of the set of vertices that are at distance greater than \(k\) from \(H\), and the \(k\)-excess \(e_k(h)\) of all \(A\)-subsets of vertices is defined as

\[e_k(h) = \max_{H \subset V(\Gamma),|H|=h} \{ e_k(H) \}\]

The \(k\)-excess \(e_k\) of the graph is obtained from \(e_k(h)\) when \(h = 1\). Here we obtain upper bounds for \(e_k(h)\) and \(e_k\) in terms of the Laplacian eigenvalues of \(\Gamma\).

Let \(G\) be a \(k\)-connected graph and let \(F\) be the simple graph obtained from \(G\) by removing the edge \(xy\) and identifying \(x\) and \(y\) in such a way that the resulting vertex is incident to all those edges (other than \(xy\)) which are originally incident to \(x\) or \(y\). We say that \(e\) is contractible if \(F\) is \(k\)-connected. A bowtie is the graph consisting of two triangles with exactly one vertex in common. We prove that if a \(k\)-connected graph \(G\) (\(k \geq 4\)) has no contractible edge, then there exists a bowtie in \(G\).

We prove that the number of nonisomorphic minimal \(2\)-colorings of the edges of \(K_{4n+3}\) is at least \(2n\) less than the number of nonisomorphic minimal \(2\)-colorings of the edges of \(K_{4n+2}\), where \(n\) is a nonnegative integer. Harary explicitly gave all the nonisomorphic minimal \(2\)-colorings of the edges of \(K_6\). In this paper, we give all the nonisomorphic minimal \(2\)-colorings of the edges of \(K_7\).

We restate a recent improvement of the inclusion-exclusion principle in terms of valuations on distributive lattices and present a completely new proof of the result. Moreover, we establish set-theoretic identities and logical equivalences of inclusion-exclusion type, which have not been considered before.

Let \(\delta(G)\) denote the minimum degree of a graph \(G\). We prove that for \(t \geq 4\) and \(k \geq 2\), a graph \(G\) of order at least \((t + 1)k + 2t^2 – 4t + 2\) with \(\delta(G) \geq k+t- 1\) contains \(k\) pairwise vertex-disjoint \(K_{1,t}\)’s.

In this paper, we construct a squag \(SQG(3n)\) of cardinality \(3n\) that contains three given arbitrary squags \(SQG(n)\)s as disjoint subquags. Accordingly, we can construct a subdirectly irreducible squag \(SQG(3n)\), for each \(n \geq 7\), with \(n \equiv 0, 3 \pmod{6}\). Also, we want to review the shape of the congruence lattice of non-simple squags \(SQG(n)\) for some \(n\) and to give a classification of the class of all \(SQG(21)\)s and the class of all \(SQG(27)\)s according to the shape of its congruence lattice. \(SQG(21)\)s are classified into three classes and \(SQG(27)\)s are classified into four classes. The construction of \(SQG(3n)\), which is given in this paper, helps us to construct examples of each class of both \(SQG(21)\)s and \(SQG(27)\)s.

We show how to produce algebraically a complete orthogonal set of Latin squares from a left quasifield and how to generate algebraically a maximal set of self-orthogonal Latin squares from a left nearfield.

A \((k;g)\)-graph is a \(k\)-regular graph with girth \(g\). A \((k; g)\)-cage is a \((k; g)\)-graph with the least possible number of vertices. In this paper, we prove that all \((4; g)\)-cages are \(4\)-connected, a special case of the conjecture about \((k; g)\)-cages’ connectivity made by H.L. Fu \(et\; al [1]\).

A set \(S\) of vertices of a graph \(G\) is a total dominating set if every vertex of \(V(G)\) is adjacent to some vertex in \(S\). The total domination number \(\gamma_t(G)\) is the minimum cardinality of a total dominating set of \(G\). Let \(G\) be a spanning subgraph of \(K_{s,s}\), and let \(H\) be the complement of \(G\) relative to \(K_{s,s}\); that is, \(K_{s,s} = G \oplus H\) is a factorization of \(K_{s,s}\). The graph \(G\) is \(k\)-critical relative to \(K_{s,s}\) if \(\gamma_t(G) = k\) and \(\gamma_t(G + e) < k\) for all \(e \in E(H)\). We study \(k_t\)-critical graphs relative to \(K_{s,s}\) for small values of \(k\). In particular, we characterize the \(3\)-critical and \(4_t\)-critical graphs.

Let \(S\) be a nonempty subset of the cyclic group \(\mathbb{Z}_p\), where \(p\) is an odd prime. Denote the \(n\)-fold sum of \(S\) as \(n..S\). That is,\(n..S = \{s_1 + \cdots + s_n \mid s_1, \ldots, s_n \in S\}.\) We say that \(S\) is an \((n, 0)\)-set if \(0 \notin n..S\). Let \(k, s\) be integers with \(k \geq 2\) such that \(p-1 = ks\). In this paper, we determine the number of \((k, 0)\)-sets of \(\mathbb{Z}_p\) which are in arithmetic progression and show explicitly the forms taken by those \((k, 0)\)-sets which achieve the maximum cardinality.

In this paper, necessary and sufficient conditions are given for the existence of extended \(5\)-cycle systems of order \(n\) which have \(r\) idempotent elements.

An \((f,2)\)-graph is a multigraph \(G\) such that each vertex of \(G\) has degree either \(f\) or \(2\). Let \(S(n, f)\) denote the simple graph whose vertex set is the set of unlabeled \((f,2)\)-graphs of order no greater than \(n\) and such that \(\{G, H\}\) is an edge in \(S(n, f)\) if and only if \(H\) can be obtained from \(G\) by either an insertion or a suppression of a vertex of degree \(2\). We also consider digraphs whose nodes are labeled or unlabeled \((f, 2)\)-multigraphs and with arcs \((G, H)\) defined as for \(\{G, H\}\).

We study the structure of these graphs and digraphs. In particular, the diameter of a given component is determined. We conclude by defining a random process on these digraphs and derive some properties. Chemistry applications are suggested.

Given a coloring \(f\) of Euclidean space \(\mathbb{R}^n\) and some group \(G\) of its transformations, its subsets \(A\) and \(B\) are said to be colored similarly, if there exists \(g \in G\), such that \(B = g(A)\) and \(f(a) = f(g(a))\), for all \(a \in A\). From our earlier result [12] it follows that there are \(2\)-colorings of \(\mathbb{R}^n\), in which no two different line segments are colored similarly with respect to isometries. The main purpose of this paper is to investigate other types of such pattern avoiding colorings. In particular, we consider topological as well as measure theoretic aspects of the above scene. Our motivation for studying this topic is twofold. One is that it extends square-free colorings of \(\mathbb{R}\), introduced in [2] as a continuous version of the famous non-repetitive sequences of Thue. The other is its relationship to some exciting problems and results of Euclidean Ramsey Theory, especially those concerning avoiding distances.

In this paper, a definition of perfect binary matroids is considered and it is shown that, analogous to the Perfect Graph Theorem of Lovász and Fulkerson, the complement of a perfect matroid is also a perfect matroid. In addition, the classes of critically imperfect graphic matroids and critically imperfect graphs are compared.

A \((p,q)\) graph \(G\) is edge-magic if there exists a bijective function \(f : V(G) \cup E(G) \to \{1,2,\ldots,p+q\}\) such that \(f(u) + f(v) + f(uv) = k\) is a constant, called the valence of \(f\), for any edge \(uv\) of \(G\). Moreover, \(G\) is said to be super edge-magic if \(f(V(G)) = \{1,2,\ldots,p\}\). Every super edge-magic \((p,q)\) graph is cordial, and it is harmonious and sequential whenever it is a tree or \(q \geq p\). In this paper, it is shown to be edge-antimagic as well. The super edge-magic properties of several classes of connected and disconnected graphs are studied. Furthermore, we prove that there can be arbitrarily large gaps among the possible valences for certain super edge-magic graphs. We also establish that the disjoint union of multiple copies of a super edge-magic linear forest is super edge-magic if the number of copies is odd.

In this paper, necessary and sufficient conditions are given for the metamorphosis of a \(\lambda\)-fold \(K_{3,3}\)-design of order \(n\) into a \(\lambda\)-fold \(6\)-cycle system of order \(n\), by retaining one \(6\)-cycle subgraph from each copy of \(K_{3,3}\), and then rearranging the set of all the remaining edges, three from each \(K_{3,3}\), into further \(6\)-cycles so that the result is a \(\lambda\)-fold \(6\)-cycle system.

Partially balanced diallel cross block designs with \(m\) associate classes are defined and two general methods of construction are presented. Two-associate class designs based upon group divisible, triangular, and extended group divisible association schemes obtained using the general methods are also given. Tables of designs for no more than \(24\) parental lines are provided.

Given a non-planar graph \(G\) with a subdivision of \(K_5\) as a subgraph, we can either transform the \(K_5\)-subdivision into a \(K_{3,3}\)-subdivision if it is possible, or else we obtain a partition of the vertices of \(G\backslash K_5\) into equivalence classes. As a result, we can reduce a projective planarity or toroidality algorithm to a small constant number of simple planarity checks [6] or to a \(K_{3,3}\)-subdivision in the graph \(G\). It significantly simplifies algorithms presented in [7], [10], and [12]. We then need to consider only the embeddings on the given surface of a \(K_{3,3}\)-subdivision, which are much less numerous than those of \(K_5\).

Let \(M(d,n)\) denote the minimax number of group tests required for the identification of the \(d\) defectives in a set of \(n\) items. It was conjectured by Hu, Hwang, and Wang that \(M(d,n) = n-1\) for \(n \leq 3d\), a surprisingly difficult combinatorial problem with very little known. The best known result is \(M(d,n) = n-1\) for \(n \leq \frac{42}{16}d\) by Du and Hwang. In this note, we improve their result by proving \(M(d,n) = n – 1\) for \(d \geq 193\) and \(n \leq \frac{42}{16}d\).

In this paper, we investigate the divisibility of \(mn\) by \(am+bn+c\) for given \(a\), \(b\), and \(c\). We give the necessary and sufficient condition for the divisibility, that is, \(am + bn + c\) divides \(mn\). We then present the structure of the set of pairs \([m,n]\) that satisfies the divisibility. This structure is represented by a directed graph and we prove the necessary and sufficient condition for the graph to have a binary tree structure. In particular, for \(c = -1\), we show double binary tree structures on the set.

Let \({PG}(n,q)\) be the projective \(n\)-space over the Galois field \({GF}(q)\). A \(k\)-cap in \({PG}(n,q)\) is a set of \(k\) points such that no three of them are collinear. A \(k\)-cap is said to be complete if it is maximal with respect to set-theoretic inclusion. In this paper, using classical algebraic varieties, such as Segre varieties and Veronese varieties, some new infinite classes of caps are constructed.

We introduce Skolem arrays, which are two-dimensional analogues of Skolem sequences. Skolem arrays are ladders which admit a Skolem labelling in the sense of [2]. We prove that they exist exactly for those integers \(n = 0\) or \(1 \pmod{4}\). In addition, we provide an exponential lower bound for the number of distinct Skolem arrays of a given order. Computational results are presented which give an exact count of the number of Skolem arrays up to order \(16\).

The cyclicity of a graph is the largest integer \(n\) for which the graph is contractible to the cycle on \(n\) vertices. We prove that, for \(n\) greater than three, the problem of determining whether an arbitrary graph has cyclicity \(n\) is NP-hard. We conjecture that the case \(n = 3\) is decidable in polynomial time.

We provide a hierarchy, linearly ordered by inclusion, describing various complete sets of combinatorial objects starting with complete sets of mutually orthogonal Latin squares, generalizing to affine geometries and designs, frequency squares and hypercubes, and ending with \((t, m, s)\)-nets.

In this paper we introduce the edge-residual number \(\rho(G)\) of a graph \(G\). We give tight upper bounds for \(\rho(G)\) in terms of the eigenvalues of the Laplacian matrix of the line graph of \(G\). In addition, we investigate the relation between this novel parameter and the line completion number for dense graphs. We also compute the line completion number of complete bipartite graphs \(K_{m,n}\) when either \(m = n\) or both \(m\) and \(n\) are even numbers. This partially solves an open problem of Bagga, Beinecke and Varma [2].

We reintroduce the problem of finding square \(\pm 1\)-matrices, denoted \(c\text{-} {H}(n)\), of order \(n\), whose rows have non-zero inner product \(c\). We obtain some necessary conditions for the existence of \(c\text{-} {H}(n)\) and provide a characterization in terms of SBIBD parameters. Several new \(c\text{-} {H}(n)\) constructions are given and new connections to Hadamard matrices and \(D\)-optimal designs are also explored.

For an integer \(k \geq 1\), a vertex \(v\) of a graph \(G\) is \(k\)-geodominated by a pair \(z, y\) of vertices in \(G\) if \(d(x, y) = k\) and \(v\) lies on an \(x-y\) geodesic of \(G\). A set \(S\) of vertices of \(G\) is a \(k\)-geodominating set if each vertex \(v\) in \(V – S\) is \(k\)-geodominated by some pair of distinct vertices of \(S\). The minimum cardinality of a \(k\)-geodominating set of \(G\) is its \(k\)-geodomination number \(g_k(G)\).

A vertex \(v\) is openly \(k\)-geodominated by a pair \(x, y\) of distinct vertices in \(G\) if \(v\) is \(k\)-geodominated by \(x\) and \(y\) and \(v \neq x, y\). A vertex \(v\) in \(G\) is a \(k\)-extreme vertex if \(v\) is not openly \(k\)-geodominated by any pair of vertices in \(G\). A set \(S\) of vertices of \(G\) is an open \(k\)-geodominating set of \(G\) if for each vertex \(v\) of \(G\), either (1) \(v\) is \(k\)-extreme and \(v \in S\) or (2) \(v\) is openly \(k\)-geodominated by some pair of distinct vertices of \(S\). The minimum cardinality of an open \(k\)-geodominating set in \(G\) is its open \(k\)-geodomination number \(og_k(G)\).

It is shown that each triple \(a, b, k\) of integers with \(2 \leq a \leq b\) and \(k \geq 2\) is realizable as the geodomination number and \(k\)-geodomination number of some tree. For each integer \(k \geq 1\), we show that a pair \((a, n)\) of integers is realizable as the \(k\)-geodomination number (open \(k\)-geodomination number) and order of some nontrivial connected graph if and only if \(2 \leq a = n\) or \(2 \leq a \leq n – k + 1\).

We investigate how \(k\)-geodomination numbers are affected by adding a vertex. We show that if \(G\) is a nontrivial connected graph of diameter \(d\) with exactly \(l\) \(k\)-extreme vertices, then \(\{2, l\} \leq g_k(G) \leq og_k(G) \leq {3}g_k(G) – 2l\) for every integer \(k\) with \(2 \leq k \leq d\).

In \(1973\), Deuber published his famous proof of Rado’s conjecture regarding partition regular sets. In his proof, he invented structures called \((m, p, c)\)-sets and gave a partition theorem for them based on repeated applications of van der Waerden’s theorem on arithmetic progressions. In this paper, we give the complete proof of Deuber’s, however with the more recent parameter set proof of his partition result for \((m, p, c)\)-sets. We then adapt this parameter set proof to show that for any \(k, m, p, c\), every \(K_k\)-free graph on the positive integers contains an \((m, p, c)\)-set, each of whose rows are independent sets.

We study the weight distributions of the ternary codes of finite projective planes of order \(9\). The focus of this paper is on codewords of small Hamming weight. We show that there are many weights for which there are no codewords.

For a given sequence of nonincreasing numbers, \(\mathbf{d} = (d_1, \ldots, d_n)\), a necessary and sufficient condition is presented to characterize \(d\) when its realization is a unique labelled simple graph. If \(G\) is a graph, we consider the subgraph \(G’\) of \(G\) with maximum edges which is uniquely determined with respect to its degree sequence. We call the set of \(E(G) \setminus E(G’)\) the smallest edge defining set of \(G\). This definition coincides with the similar one in design theory.

A graph \(G\) without isolated vertices is said to be set-magic if its edges can be assigned distinct subsets of a set \(X\) such that for every vertex \(v\) of \(G\), the union of the subsets assigned to the edges incident with \(v\) is \(X\); such a set-assignment is called a set-magic labeling of \(G\). In this note, we study infinite set-magic graphs and characterize infinite graphs \(G\) having set-magic labelings \(f\) such that \(|f(e)| = 2\) for all \(e \in E(G)\).

A perfect \(\langle k,r \rangle\)-latin square \(A = (a_{i,j})\) of order \(n\) with \(m\) elements is an \(n \times n\) array in which each element occurs in each row and column, and the element \(a_{i,j}\) occurs either \(k\) times in row \(i\) and \(r\) times in column \(j\), or occurs \(r\) times in row \(i\) and \(k\) times in column \(j\). In 1989, Cai, Kruskal, Liu, and Shen studied the existence of perfect \(\langle k,r \rangle\)-latin squares. Here, a simpler construction of perfect \(\langle k,r \rangle\)-latin squares is given.

De Bruijn sequences had been well investigated in \(70s-80s\). In the past, most of the approaches used to generate de Bruijn sequences were based upon either finite field theory or combinatorial theory. This paper describes a simple approach for generating de Bruijn sequences as “seeds”, and then based upon the “seeds”, a simple procedure is presented to reproduce a class of de Bruijn sequences. Numerical results of the distribution of reproduced sequences are provided. Additionally, this paper also reports some recent applications of de Bruijn sequences in psychology and engineering.

A graph \(G(V, E)\) is a mod sum graph if there is a labeling of the vertices with distinct positive integers so that an edge is present if and only if the sum of the labels of the vertices incident on the edge, modulo some positive integer, is the label of a vertex of the graph. It is known that wheels are not mod sum graphs. The mod sum number of a graph is the minimum number of isolates that, together with the given graph, form a mod sum graph. The mod sum number is known for just a few classes of graphs. In this paper we show that the mod sum number of the \(n\)-spoked wheel, \(\rho(W_n)\), \(n \geq 5\), is \(n\) when \(n\) is odd and \(2\) when \(n\) is even.

Kahn (see [3]) reported that N. Alon, M. Saks, and P. D. Seymour made the following conjecture. If the edge set of a graph \(G\) is the disjoint union of the edge sets of \(m\) complete bipartite graphs, then \(\chi(G) \leq m+1\). The purpose of this paper is to provide a proof of this conjecture for \(m \leq 4\) and \(m \geq n – 3\) where \(G\) has \(n\) vertices.

In a graph \(G = (V, E)\), a set \(S\) of vertices (as well as the subgraph induced by \(S\)) is said to be dominating if every vertex in \(V \setminus S\) has at least one neighbor in \(S\). For a given class \(\mathcal{D}\) of connected graphs, it is an interesting problem to characterize the class \({Dom}(\mathcal{D})\) of graphs \(G\) such that each connected induced subgraph of \(G\) contains a dominating subgraph belonging to \(\mathcal{D}\). Here we determine \({Dom}(\mathcal{D})\) for \(\mathcal{D} = \{P_1, P_2, P_5\}\), \(\mathcal{D} = \{K_t \mid t \geq 1\} \cup \{P_5\}\), and \(\mathcal{D} =\) {connected graphs on at most four vertices} (where \(P_t\) and \(K_t\) denote the path and the complete graph on \(t\) vertices, respectively). The third theorem solves a problem raised by Cozzens and Kelleher [\(Discr. Math.\) 86 (1990), 101-116]. It turns out that, in each case, a concise characterization in terms of forbidden induced subgraphs can be given.

We use the results on \(5\)-GDDs to obtain optimal packings with block size five and index one. In particular, we prove that if \(v \equiv 2, 6, 10 \pmod{20}\), there exists an optimal packing with block size five on \(v\) points with at most \(32\) possible exceptions. Furthermore, if \(v \equiv 14, 18 \pmod{20}\), there exists an optimal packing with block size five on \(v\) points with a finite (large) number of possible exceptions.

A chromatic root is a root of the chromatic polynomial of some graph \(G\). E. Farrell conjectured in \(1980\) that no chromatic root can lie in the left-half plane, and in \(1991\) Read and Royle showed by direct computation that the chromatic polynomials of some graphs do have a root there. These examples, though, yield only finitely many such chromatic roots. Subsequent results by Shrock and Tsang show the existence of chromatic roots of arbitrarily large negative real part. We show that theta graphs with equal path lengths of size at least \(8\) have chromatic roots with negative real part.

The clique operator \(K\) maps a graph \(G\) into its clique graph, which is the intersection graph of the (maximal) cliques of \(G\). Recognizing clique graphs is a problem known to be in NP, but no polynomial time algorithm or proof of NP-completeness is known. In this note we prove that this recognition problem can be reduced to the case of graphs of diameter at most two.

The skewness of a graph \(G\) is the minimum number of edges that need to be deleted from \(G\) to produce a planar graph. The splitting number of a graph \(G\) is the minimum number of splitting steps needed to turn \(G\) into a planar graph; where each step replaces some of the edges \(\{u,v\}\) incident to a selected vertex \(u\) by edges \(\{u’,v\}\), where \(u’\) is a new vertex. We show that the splitting number of the toroidal grid graph \(C_n \times C_m\) is \(\min\{n,m\} – 2\delta_{n,3}\delta_{m,3} – \delta_{n,4}\delta_{m,3} – \delta_{n,3}\delta_{m,4}\) and its skewness is \(\min\{n, m\} – \delta_{n,3}\delta_{m,3 }- \delta_{n,4}\delta_{m,3} – \delta_{n,3}\delta_{m,4}\). Here, \(\delta\) is the Kronecker symbol, i.e., \(\delta_{i,j}\) is \(1\) if \(i = j\), and \(0\) if \(i \neq j\).

We introduce the notion of BP-spatial representation of a biconnected graph \(G = (V, E)\). We show that the spatiality degree of a BP-spatial representable graph is \(2(|E| – |V|)\). From this result, we derive the spatiality degree for planar and hamiltonian graphs.

We introduce the notion of premature partial Latin squares; these cannot be completed, but if any of the entries is deleted, a completion is possible. We study their spectrum, i.e., the set of integers \(t\) such that there exists a premature partial Latin square of order \(n\) with exactly \(t\) nonempty cells.

Given a digraph \(D\), its competition graph has the same vertex set and an edge between two vertices \(x\) and \(y\) if there is a vertex \(u\) so that \((x,u)\) and \((y,u)\) are arcs of \(D\). Motivated by a problem of communications, we study the competition graphs of the special digraphs known as semiorders. This leads us to define a condition on digraphs called \(C(p)\) and \(C^*(p)\) and to study the graphs arising as competition graphs of acyclic digraphs satisfying conditions \(C(p)\) or \(C^*(p)\).

A transversal cover is a set of \(gk\) points in \(k\) disjoint groups of size \(g\) and, ideally, a minimal collection of transversal subsets, called blocks, such that any pair of points not contained in the same group appears in at least one block. In this article we present a direct construction method for transversal covers using group divisible designs. We also investigate a particular infinite family of group divisible designs that yield particularly good covers.

For an ordered set \(A\) and \(B\) whose orders agree on its intersection, the gluing of \(A\) and \(B\) is defined to be the ordered set on the union of its underlying sets whose order is the transitive closure of the union of the orders of \(A\) and \(B\). The gluing number of an ordered set \(P\) is the minimum number of induced semichains (suborders of dimension at most two) of \(P\) whose consecutive gluing is \(P\). In this paper we investigate this parameter on some special ordered sets.

The aim of this paper is to give several characterizations for the following two classes of graphs: (i) graphs for which adding any \(l\) edges produces a graph which is decomposable into \(k\) spanning trees and (ii) graphs for which adding some \(l\) edges produces a graph which is decomposable into \(k\) spanning trees.

Upper and lower bounds are given for the toughness of generalized Petersen graphs. A lower bound of \(1\) is established for \(t(G(n,k))\) for all \(n\) and \(k\). This bound of \(1\) is shown to be sharp if \(n = 2k\) or if \(n\) is even and \(k\) is odd. The upper bounds depend on the parity of \(k\). For \(k\) odd, the upper bound \(\frac{n}{n-\frac{n+1}{2}}\) is established. For \(k\) even, the value \(\frac{2k}{2k-1}\) is shown to be an asymptotic upper bound. Computer verification shows the reasonableness of these bounds for small values of \(n\) and \(k\).

Suppose \(G\) is a graph. The minimum number of paths (trees, forests, linear forests, star forests, complete bipartite graphs, respectively) needed to decompose the edges of \(G\) is called the path number (tree number, arboricity, linear arboricity, star arboricity and biclique number, respectively) of \(G\). These numbers are denoted by \(p(G), t(G), a(G), la(G), sa(G), r(G)\), respectively. For integers \(1 \leq k \leq n\), let \(C_{n,k}\) be the graph with vertex set \(\{a_1,a_2,\ldots,a_n,b_1,b_2,\ldots,b_n\}\) and edge set \(\{a_ib_j :i=1,2,\ldots ,n,j \equiv i+1,i+2, \ldots ,i+k \text{(mod n)}\}\). We call \(C_{n,k}\) a crown. In this paper, we prove the following results:

1. \(p(C_{n,k}) = \begin{cases}
   n & \text{if \(k\) is odd}, \\
   {(\frac{k}{2})+1} & \text{if \(k\) is even}.
   \end{cases}\)
2. \(a(C_{n,k}) = t(C_{n,k}) = la(C_{n,k}) = \left\lceil \frac{k+1}{2} \right\rceil\) if \(k \geq 2\).
3. For \(k \geq 3\) and \(k \in \{3,5\} \cup \{n-3,n-2,n-1\}\),
   \[sa(C_{n,k}) = \begin{cases}
   \left\lceil \frac{k}{2} \right\rceil + 1 & \text{if \(k\) is odd}, \\
   \left\lceil \frac{k}{2} \right\rceil + 2 & \text{if \(k\) is even}.
   \end{cases}\]
4. \(r(C_{n,k}) = n\) if \(k \leq \frac{n+1}{2}\) or \(\gcd(k,n) = 1\).

Due to (3), (4), we propose the following conjectures.

\(\textbf{Conjecture A}\). For \(3 \leq k \leq n-1\),
\[sa(C_{n,k}) = \begin{cases}
\left\lceil \frac{k}{2} \right\rceil + 1 & \text{if \(k\) is odd}, \\
\left\lceil \frac{k}{2} \right\rceil + 2 & \text{if \(k\) is even}.
\end{cases}\]
\(\textbf{Conjecture B}\). For \(1 \leq k \leq n-1\), \(r(C_{n,k}) = n\).

Let \(G = (V, E)\) be a graph and \(A\) a non-trivial Abelian group, and let \(\mathcal{F}(G, A)\) denote the set of all functions \(f: E(G) \to A\). Denote by \(D\) an orientation of \(E(G)\). Then \(G\) is \(A\)-colorable if and only if for every \(f \in \mathcal{F}(G, A)\) there exists an \(A\)-coloring \(c: V(G) \to A\) such that for every \(e = (x,y) \in E(G)\) (assumed to be directed from \(x\) to \(y\)), \(c(x) – c(y) \neq f(e)\). If \(G\) is a graph, we define its group chromatic number \(\chi_1(G)\) to be the minimum number \(m\) for which \(G\) is \(A\)-colorable for any Abelian group \(A\) of order \(\geq m\) under the orientation \(D\). In this paper, we investigated the properties of the group chromatic number, proved the Brooks Type theorem for \(\chi_1(G)\), and characterized all bipartite graphs with group chromatic number at most \(3\), among other things.

A signed graph is an unoriented graph with a given partition \(E = E^+ \bigcup E^-\) of its edge-set. We define the arc signed graph \({A}(G)\) of an oriented graph \(G\) (G has no multiple arcs, opposite arcs, and loops). The arc signed graphs are similar to the line graphs. We prove both a Krausz-type characterization and a forbidden induced subgraph characterization (like the theorem of Beineke and Robertson on line graphs). Unlike line graphs, there are infinitely many minimal forbidden induced subgraphs for the arc signed graphs. Nevertheless, the arc signed graphs are polynomially recognizable. Also, we obtain a result similar to Whitney’s theorem on line graphs.

For a vertex \(v\) in a graph \(G\), we denote by \(N^2(v)\) the set \((N_1(N_1(v))\setminus \{v\})\cup N_1(v)=\{x\in V(G): 1 \leq d(x,v) \leq 2\}\), where \(d(x,v)\) denotes the distance between \(x\) and \(v\). A vertex \(v\) is \(N^2\)-locally connected if the subgraph induced by \(N^2(v)\) is connected. A graph \(G\) is called \(N^2\)-locally connected if every vertex of \(G\) is \(N^2\)-connected. A well-known result by Oberly and Sumner is that every connected locally connected claw-free graph on at least three vertices is Hamiltonian. This result was improved by Ryjacek using the concept of second-type neighborhood. In this paper, using the concept of \(N^2\)-locally connectedness, we show that every connected \(N^2\)-locally connected claw-free graph \(G\) without vertices of degree \(1\), which does not contain an induced subgraph \(H\) isomorphic to one of \(G_1, G_2, G_3\), or \(G_4\), is Hamiltonian, hereby generalizing the result of Oberly and Sumner (J. Graph Theory, \(3 (1979) 351-356\))and the result of \(Ryjacek\)( J. Graph Theory, \(14 (1990)\) 321-381)

On the gracefulness of graph \(C_m\bigcup P_n\), Frucht and Salinas that proved \(C_m\bigcup P_n\) is graceful and conjectured: \(C_m\bigcup P_n\) is graceful if and only if \(m+n=7\). In this paper, we prove graph \(C_m\bigcup P_n\) is graceful, for \(m=4k, n=k+2, k+3, 2k+1,\ldots, 2k+5;\) \(m=4k+1, n=2k, 3k+1, 4k+1;\) \(m=4k+2 n=3k, 3k+1,
4k+1; m=4k+3, n=2k+1, 3k, 4k\).

Let \(\nu(\mathbb{Z}^m)\) be the minimal number of colors enough to color the \(m\)-dimensional integer grid \(\mathbb{Z}^m\) so that there would be no infinite monochromatic symmetric subsets. Banakh and Protasov [3] compute \(\nu(\mathbb{Z}^m) = m+1\). For the one-dimensional case this just means that one can color positive integers in red, while negative integers in blue, thereby avoiding an infinite monochromatic symmetric subset by a trivial reason. This motivates the question what changes if we allow only colorings unlimited in both directions (in “all” directions for \(m > 1\)). In this paper we show that then \(\nu(\mathbb{Z})\) increases by \(1\), whereas for higher dimensions the values \(\nu(\mathbb{Z}^m)\) remain unaffected.
Furthermore we examine the density properties of a set \(A \subseteq \mathbb{Z}^m\) that ensure the existence of infinite symmetric subsets or arbitrarily large finite symmetric subsets in \(A\). In the case that \(A\) is a sequence with small gaps, we prove a multi-dimensional analogue of the Szemerédi theorem, with symmetric subsets in place of arithmetic progressions. A similar two-dimensional statement is known for collinear subsets (Pomerance [10]), whereas for two-dimensional arithmetic progressions even the corresponding version of van der Waerden’s theorem is known to be false.

The eccentricity of a vertex \(v\) in a connected graph \(G\) is the distance between \(v\) and a vertex farthest from \(v\). For a vertex \(v\), we define the edge-added eccentricity of \(v\) as the minimum eccentricity of \(v\) in all graphs \(G+e\), taken over all edges \(e\) in the complement of \(G\). A graph is said to be edge-added stable (or just stable) if the eccentricity and the edge-added eccentricity are the same for all vertices in the graph. This paper describes properties of edge-added eccentricities and edge-added stable graphs.

In this paper, we find explicit formulas or generating functions for the cardinalities of the sets \(S_n(T,\tau)\) of all permutations in \(S_n\) that avoid a pattern \(\tau \in S_k\) and a set \(T, |T| \geq 2,\) of patterns from \(S_3\). The main body of the paper is divided into three sections corresponding to the cases \(|T| = 2, 3\) and \(|T| \geq 4\). As an example, in the fifth section, we obtain the complete classification of all cardinalities of the sets \(S_n(T,\tau)\) for \(k = 4\).

The concept of weakly associative lattices (i.e. relational systems with a reflexive and antisymmetric relation \(\leq\), in which for each pair of elements there exist a least upper and a greatest lower bound) was introduced in [3] and [5]. In [4] WU-systems are defined, i.e. weakly associative lattices with the unique bound property, and their equivalence with projective planes is described. In this paper we introduce WU\(_{\lambda}\)-systems, and discuss their relation to symmetric \(2\)-\((v,k,\lambda)\) designs equipped with a special “loop-free” mapping.

It is shown in this paper that every \(2\)-connected claw-free graph containing a \(k\)-factor has a connected \([k,k+1]\)-factor, where \(k \geq 2\).

Let \(G\) be a graph of order \(n\), and let \(n = \sum_{i=1}^{k}a^i\) be a partition of \(n\) with \(a_i \geq 2\). Let \(v_1, \ldots, v_k\) be given distinct vertices of \(G\). Suppose that the minimum degree of \(G\) is at least \(3k\). In this paper, we prove that there exists a decomposition of the vertex set \(V(G) = \bigcup_{i=1}^k A_i\) such that \(|A_i| = a_i\), \(v_i \in A_i\), and the subgraph induced by \(A_i\) contains no isolated vertices for all \(i, 1 \leq i \leq k\).

Let \(G\) be a graph of order \(n \geq 4k\) and let \(S\) be the graph obtained from \(K_4\) by removing two edges which have a common vertex. In this paper, we prove the following theorem:
A graph \(G\) of order \(n \geq 4k\) with \(\sigma_2(G) \geq n+k\) has \(k\) vertex-disjoint \(S\).This theorem implies that a graph \(G\) of order \(n = 4k\) with \(\sigma_2(G) \geq 5k\) has an \(S\)-factor.

The reconstruction number \(rn(G)\) of graph \(G\) is the minimum number of vertex-deleted subgraphs of \(G\) required in order to identify \(G\) up to isomorphism. Myrvold and Molina have shown that if \(G\) is disconnected and not all components are isomorphic then \(rn(G) = 3\), whereas, if all components are isomorphic and have \(c\) vertices each, then \(rn(G)\) can be as large as \(c + 2\). In this paper we propose and initiate the study of the gap between \(rn(G) = 3\) and \(rn(G) = c + 2\). Myrvold showed that if \(G\) consists of \(p\) copies of \(K_c\), then\(rn(G) = c + 2\). We show that, in fact, this is the only class of disconnected graphs with this value of \(rn(G)\). We also show that if \(rn(G) \geq c + 1\) (where \(c\) is still the number of vertices in any component), then, again, \(G\) can only be copies of \(K_c\). It then follows that there exist no disconnected graphs \(G\) with \(c\) vertices in each component and \(rn(G) = c + 1\). This poses the problem of obtaining for a given \(c\), the largest value of \(t = t(c)\) such that there exists a disconnected graph with all components of order \(c\), isomorphic and not equal to \(K_c\), and is such that \(rn(G) = t\).

We take a special \(1\)-factorization of \(K_{n,n}\), and investigate the subgraphs suborthogonal to the \(1\)-factorization. Some interesting results are obtained, including an identity involving \(n^n\) and \(n!\) and a property of permutations.

An extended Mendelsohn triple system of order \(v\) (EMTS(\(v\))) is a collection of cyclically ordered triples of the type \([x,y,z], [x,x,y]\), or \([x,x,x]\) chosen from a \(v\)-set, such that each ordered pair (not necessarily distinct) belongs to exactly one triple. If such a design with parameters \(v\) and \(a\) exist, then they will have \(b_{v,a}\) blocks, where \(b_{v,a} = (v^2 + 2a)/3\). In this paper, we show that there are two (not necessarily distinct) EMTS(\(v\))’s with common triples in the following sets:

\(\{0,1,2,\ldots,b_v-4,b_v-2,b_v\}\), if \(v \neq 6\); and

\(\{0,1,2,\ldots,b_v-4,b_v-2\}\), if \(v = 6\),

where \(b_v\) is \(b_{v,v-1}\) if \(v \equiv 2 \pmod{3}\); \(b_{v,v}\) if \(v \not\equiv 2 \pmod{3}\).

Dudeney’s round table problem was proposed about one hundred years ago. It is already solved when the number of people is even, but it is still unsettled except for only a few cases when the number of people is odd.

In this paper, a solution of Dudeney’s round table problem is given when \(n = p+2\), where \(p\) is an odd prime number such that \(2\) is the square of a primitive root of \(\mathrm{GF}(p)\), and \(p \equiv 3 \pmod{4}\).

The number \(g^{(4)}_{2}\) is the minimal number of blocks that contain all pairs from a set of \(8\) elements exactly twice under the restriction that the longest block has size \(4\) (this longest block need not be unique). Thus the blocks have lengths \(2, 3\), and \(4\). We show that there are three solutions to this problem.

The \(n \times n\) primitive nearly reducible Boolean matrices whose \(k\)-exponents (\(1 \leq k \leq n\)) achieve the maximum value are characterized.

A graph is said to be \(k\)-covered if for each edge \(xy\), \(deg(x) = k\) or \(deg(y) = k\). In this paper, we characterize the \(3\)-covered quadrangulations of closed surfaces.

A graceful graph with \(n\) edges and \(n+1\) vertices is called a vertex-saturated graph. Each graceful graph corresponds to a vertex-saturated graph. Four classes of graceful graphs associated with vertex-saturated graphs are presented. Three of which generalize the results of [1], [2] and [5].

We correct an earlier theorem and reprove its consequences regarding \(c\)-BRDs with \(v \equiv 5, 8 \pmod{12}\). The original conclusions remain valid.

The type of a vertex \(v\) in a \(p\)-page book-embedding is the \(p \times 2\) matrix of nonnegative integers

\[{r}(v) =
\left(
\begin{array}{ccccc}
l_{v,1} & r_{v,1} \\
. & . \\
. & . \\
. & . \\
l_{v,p} & r_{v,p} \\
\end{array}
\right),\]

where \(l_{v,i}\) (respectively, \(r_{v,i}\)) is the number of edges incident to \(v\) that connect on page \(i\) to vertices lying to the left (respectively, to the right) of \(v\). The type number of a graph \(G\), \(T(G)\), is the minimum number of different types among all the book-embeddings of \(G\). In this paper, we disprove the conjecture by J. Buss et al. which says for \(n \geq 4\), \(T(L_n)\) is not less than \(5\) and prove that \(T(L_n) = 4\) for \(n \geq 3\).

Let \(T\) be a chemical tree, i.e. a tree with all vertices of degree less than or equal to \(4\). We find relations for the \(0\)-connectivity and \(1\)-connectivity indices \({}^0\chi(T)\) and \({}^1\chi(T)\), respectively, in terms of the vertices and edges of \(T\). A comparison of these relations with the coefficients of the characteristic polynomial of \(T\) associated to its adjacency matrix is established.

Given a regular action of a finite group \(G\) on a set \(V\), we consider the problem of the existence of an incidence structure \(\mathcal{I} = (V, \mathcal{B})\) on the set \(V\) whose full automorphism group \(Aut(\mathcal{I})\) is the group \(G\) in its regular action. Using results on graphical and digraphical regular representations \(([2,7], [1])\), we show the existence of such an incidence structure for all but four small finite groups.

For a finite field \({F} = {F}(q)\), where \(q = p^n\) is a prime power, we will introduce the notion of equivalence of subsets of \(F\) which stems out of the equivalence of cyclic difference sets, and give the formulae for the number of equivalence classes of \(k\)-subsets of \(F\) as well as for the number of equivalence classes of subsets of \(F\) by using Pólya’s theorem of counting.

We present an algorithmic construction of anti-Pasch Steiner triple systems for orders congruent to \(9\) mod \(12\). This is a Bose-type method derived from a particular type of \(3\)-triangulations generated from non-sum-one-difference-zero sequences (\(NS1D0\) sequences). We introduce \(NS1D0\) sequences and describe their basic properties; in particular, we develop an equivalence between the problem of finding \(NS1D0\) sequences and a variant of the \(n\)-queens problem. This equivalence, and an algebraic characterization of the \(NS1D0\) sequences that produce anti-Pasch Steiner triple systems, form the basis of our algorithm.

For vertices \(u\) and \(v\) in a nontrivial connected graph \(G\), the closed interval \([u,v]\) consists of \(u\), \(v\), and all vertices lying in some \(u-v\) geodesic of \(G\). For \(S \subseteq V(G)\), the set \(I[S]\) is the union of all sets \(I[u,v]\) for \(u,v \in S\). A set \(S\) of vertices of a graph \(G\) is a geodetic set in \(G\) if \(I[S] = V(G)\). The minimum cardinality of a geodetic set in \(G\) is its geodetic number \(g(G)\). A subset \(T\) of a minimum geodetic set \(S\) in a graph \(G\) is a forcing subset for \(S\) if \(S\) is the unique minimum geodetic set containing \(T\). The forcing geodetic number \(f(S)\) of \(S\) in \(G\) is the minimum cardinality of a forcing subset for \(S\), and the upper forcing geodetic number \(f^+(G)\) of the graph \(G\) is the maximum forcing geodetic number among all minimum geodetic sets of \(G\). Thus \(0 \leq f^+(G) \leq g(G)\) for every graph \(G\). The upper forcing geodetic numbers of several classes of graphs are determined. It is shown that for every pair \(a,b\) of integers with \(0 \leq a \leq b\) and \(b \geq 1\), there exists a connected graph \(G\) with \(f^+(G) = a\) and \(g(G) = b\) if and only if \((a, b) \notin \{(1, 1), (2,2)\}\).

We give necessary and sufficient conditions for the existence of a decomposition of the complete graph into stars which admits either a cyclic or a rotational automorphism.

This paper deals with combinatorial aspects of designs for two-way elimination of heterogeneity for making all possible paired comparisons of treatments belonging to two disjoint sets of treatments. Balanced bipartite row-column (BBPRC) designs have been defined which estimate all the elementary contrasts involving two treatments one from each of the two disjoint sets with the same variance. General efficiency balanced row-column designs (GEBRC) are also defined. Some general methods of construction of BBPRC designs have been given using the techniques of reinforcement, deletion (addition) of column or row structures, merging of treatments, balanced bipartite block (BBPB) designs, juxtaposition, etc. Some methods of construction give GEBRC designs also.

A critical set in a Latin square of order \(n\) is a set of entries in a Latin square which can be embedded in precisely one Latin square of order \(n\). Also, if any element of the critical set is deleted, the remaining set can be embedded in more than one Latin square of order \(n\). In this paper, we find smallest weak and smallest totally weak critical sets for all the Latin squares of orders six and seven. Moreover, we computationally prove that there is no (totally) weak critical set in the back circulant Latin square of order five and we find a totally weak critical set of size seven in the other main class of Latin squares of order five.

In this paper, we give the following labelings:

1. Elegant labelings of triangular snakes \(\Delta_{n}\) , \(n \equiv 0,1,2 \mod 4\).
2. Near-elegant labeling of triangular snakes \(\Delta_{n}\) when \(n \equiv 3 \mod 4\), which are not elegant.
3. Elegant and near-elegant labelings of some of the theta graphs \(\theta_{n,n}\) when \(n = 1, 2, 3\).
4. Harmonious labelings of helms \(H_n\) when \(n\) is even.

A linear \([n,k,d]_q\) code \(C\) is called NMDS if \(d(C) = n – k\) and \(d(C^{\perp}) = k\). In this paper, the classification of the \([n,3,n-k]_q\) NMDS codes is given for \(q = 7,8,9\). It has been found using the correspondence between \([n,3,n-k]_q\) NMDS codes and \((n,3)\)-arcs of \(\mathrm{PG}(2,q)\).

A path in a digraph is antidirected if the two adjacent edges of the path have opposing orientations. In this paper, we give a necessary and sufficient condition for the edges of the complete symmetric graph to be decomposed into isomorphic antidirected paths.

The aim of this note is to provide a programme for the Computer Algebra package MAGMA, which is suitable to decode one-point Goppa codes defined from Hermitian curves.

In this article, the intersection problem for twin bowtie and near bowtie systems is completely solved.

Given a graph, a no-hole \(2\)-distant coloring (also called \(N\)-coloring) is a function \(f\) that assigns to each vertex a non-negative integer (color) such that the separation of the colors of any pair of adjacent vertices must be at least \(2\), and all the colors used by \(f\) form a consecutive set (the no-hole assumption). The minimum consecutive \(N\)-span of \(G\), \(csp(G)\), is the minimum difference of the largest and the smallest colors used in an \(N\)-coloring of \(G\), if there exists such a coloring; otherwise, define \(csp(G) = \infty\). Here we investigate the exact values of \(csp(G)\) for unit interval graphs (also known as \(1\)-unit sphere graphs). Earlier results by Roberts [18] indicate that if \(G\) is a unit interval graph on \(n\) vertices, then \(csp_1(G)\) is either \(2\chi(G) – 1\) or \(2\chi(G) – 2\), if \(n > 2\chi(G) – 1\); \(csp_1(G) = \infty\), if \(n < 2\chi(G) – 1\), where \(\chi(G)\) denotes the chromatic number. We show that in the former case (when \(n > 2\chi(G) – 1\)), both values of \(csp_1(G)\) are attained, and give several families of unit interval graphs such that \(csp_1(G) = 2\chi(G) – 2\). In addition, the exact values of \(csp_1(G)\) are completely determined for unit interval graphs with \(\chi(G) = 3\).

Let \(G\) be a graph. Let \(\gamma\) denote the minimum cardinality of a dominating set in \(G\). Let \(\beta\), respectively \(i\), denote the maximum, respectively minimum, cardinality of a maximal independent set in \(G\). We show \(\gamma + \Delta \geq \left\lceil {2\sqrt{n}-1} \right\rceil\), where \(n\) is the number of vertices of \(G\). A straightforward construction shows that given any \(G’\) there exists a graph \(G\) such that \(\gamma(G) + \Delta(G) = \left\lceil {2\sqrt{n}-1} \right\rceil\) and \(G’\) is an induced subgraph of \(G\), making classification of these \(\gamma+\Delta\) minimum graphs difficult.

We then focus on the subclass of these graphs with the stronger condition that \(\beta + \Delta = \left\lceil {2\sqrt{n}-1} \right\rceil\). For such graphs \(i = \beta\) and thus the graphs are well-covered. If \(G\) is a graph with \(\beta + \Delta = \left\lceil {2\sqrt{n}-1} \right\rceil\), we have \(\beta = \left\lceil \frac{\sqrt{n}}{\Delta+1} \right\rceil\). We give a catalogue of all well-covered graphs with \(\Delta \leq 3\) and \(\beta = \left\lceil \frac{\sqrt{n}}{\Delta+1} \right\rceil\). Again we establish that given any \(G’\) we can construct \(G\) such that \(G’\) is an induced subgraph of \(G\) and \(G\) satisfies \(\beta = \left\lceil \frac{\sqrt{n}}{\Delta+1} \right\rceil\). In fact, the graph \(G\) can be constructed so that \(\beta(G) + \Delta(G) = \left\lceil {2\sqrt{n}-1} \right\rceil\). We remark that \(\Delta(G)\) may be much larger than \(\Delta(G’)\).

We conclude the paper by analyzing integer solutions to \(\left\lceil \frac{n}{\Delta+1} \right\rceil + \Delta = \left\lceil {2\sqrt{n}-1} \right\rceil\). In particular, for each \(n\), the values of \(\Delta\) that satisfy the equation form an interval. When \(n\) is a perfect square, this interval contains only one value, namely \(\sqrt{n}\). For each \((n, \Delta)\) solution to the equation, there exists a graph \(G\) with \(n\) vertices, maximum degree \(\Delta\), and \(\beta = \left\lceil \frac{\sqrt{n}}{\Delta+1} \right\rceil\).

We construct a family of \(p-1\) square \(p \times p\) matrices (\(p\) is any prime) whose periodic cross-correlation values are uniformly \(-p, 0, +p\) between all pairs of the matrices in the family. For every one of the matrices in the family, all the off-peak autocorrelation values are \(-p\) and \(0\), while the single peak value is \(p(p-1)\). For \(p = 127\) (where the values \(-p, 0, +p\) are below \(1\%\) of the size \(p^2\) of the matrices) utilization of this construction has resulted in the superimposed embedding of twelve of the matrices (as watermarks) in the standard image “Lenna” and their subsequent retrieval without recourse to the unmarked image.

Let \(D\) be a connected symmetric digraph, \(\Gamma\) a group of automorphisms of \(D\), and \(A\) a finite abelian group with some specified property. We discuss the number of isomorphism classes of \(g\)-cyclic \(A\)-covers of \(D\) with respect to a group \(\Gamma\) of automorphisms of \(D\). Furthermore, we enumerate the number of \(I\)-isomorphism classes of \(g\)-cyclic \(\mathbb{Z}_{2^m}\)-covers of \(D\) for the cyclic group \(\mathbb{Z}_{2^m}\) of order \(2^m\), where \(I\) is the trivial subgroup of \(Aut(D)\).

We characterize tough-maximum graphs, that is, graphs having maximum number of edges among all graphs with given number of vertices and toughness.

The toughness \(t(G)\) of a noncomplete graph \(G\) is defined as

\[t(G) = \min \left\{ \frac{|S|}{\omega(G – S)} \mid S \subset V(G), \omega(G – S) \geq 2 \right\},\]

where \(\omega(G – S)\) is the number of components of \(G – S\). We also define \(t(K_n) = +\infty\) for every \(n\).

The total graph \(T(G)\) of a graph \(G\) is the graph whose vertex set can be put in one-to-one correspondence with the set \(V(G) \cup E(G)\) such that two vertices of \(T(G)\) are adjacent if and only if the corresponding elements of \(G\) are adjacent or incident.

In this article, we study the toughness of the total graph \(T(G)\) of a graph \(G\) on at least \(3\) vertices and give especially that \(t(T(G)) = t(G)\) if \(\kappa(G) = \lambda(G)\) and \(\kappa(G) \leq 2\), where \(\kappa(G)\) and \(\lambda(G)\) are the vertex and the edge-connectivity of \(G\), respectively.

We shall consider a problem of finding an ‘optimum’ tree which is closely related to the network flow problem proposed by Ford and Fulkerson, and call the solution to this problem a lexicographically optimum traffic tree (LOTT). Before examining this problem in detail, we shall review the problem of finding an optimum requirement spanning tree (ORST) studied by Hu, which is also related to the network flow problem. We can regard the LOTT problem as a min-max problem and the ORST problem as a min-sum problem. It shall be shown that, while LOTTs and ORSTs coincide completely without maximum degree constraints, they do not always coincide with the constraints. Further, we shall show that LOTTs can be expressed by simple recursion in a special case.

It is well known that some graph-theoretic extremal questions play a significant role in the investigation of communication network vulnerability. Answering questions concerning the realizability of graph invariants also solves several of these extremal problems. We define a \((p, q, \kappa, \Delta)\) graph as a graph having \(p\) points, \(q\) lines, point connectivity \(\kappa\) and maximum degree \(\Delta\). An arbitrary quadruple of integers \((a, b, c, d)\) is called \((p, q, \kappa, \Delta)\) realizable if there is a \((p, q, \kappa, \Delta)\) graph with \(p = a, q = b, \kappa = c\) and \(\Delta = d\). Necessary and sufficient conditions for a quadruple to be \((p, q, \kappa, \Delta)\) realizable are derived. In earlier papers, Boesch and Suffel gave necessary and sufficient conditions for \((p, q, \kappa)\), \((p, q, \lambda)\), \((p, q, \delta)\), \((p, \Delta, \delta, \lambda)\) and \((p, \Delta, \delta, \kappa)\) realizability, where \(\lambda\) denotes the line connectivity of a graph and \(\delta\) denotes the minimum degree for all points in a graph.

We introduce the concept of a free \(a\)-valuation of a graph, and prove that the vertex-disjoint union of any collection of graphs with free \(\alpha\)-valuations has an \(\alpha\)-valuation. Many bipartite graphs have free \(\alpha\)-valuations, including the complete bipartite graph \(K_{m,n}\) when \(m > 1\) and \(n > 2\), and the \(d\)-cube \(Q_d\) for \(d > 2\).

Let \(G\) be a \(2\)-connected simple graph with order \(n\) (\(n \geq 5\)) and minimum degree \(5\). This paper proves that if for any two vertices \(u,v\) of \(G\) at distance two there holds \(|N(u) \bigcup N(v)| \geq n – \delta\), then \(G\) is vertex-pancyclic with a few exceptions.

Various \(n\)-color restricted partition functions are studied. Two different \(n\)-color analogues of the Gaussian polynomials are given.

There is a lexicographic ordering of \((0, 1)\)-tuples. Thus, the rows of a \((0, 1)\)-matrix can be ordered lexicographically decreasing from the top by permutations, or analogously the columns from the left. It is shown that \((0, 1)\)-matrices allow a simultaneous ordering of the rows and the columns. Those matrices are called doubly ordered, and their structure is determined. An answer is given to the question of whether a \((0, 1)\)-matrix can be transformed into a block diagonal matrix by permutations of the rows and the columns; in fact, the double ordering of a \((0, 1)\)-matrix already displays the finest block diagonal structure. Moreover, fast algorithms are presented that double order a \((0, 1)\)-matrix.