Let \(G\) be a simple graph with \(n\) vertices, and let \(\overline{G}\) denote the complement of \(G\). A well-known theorem of Nordhaus and Gaddum [6] bounds the sum \(\chi(G) + \chi(\overline{G})\) and product \(\chi(G)\chi(\overline{G})\) of the chromatic numbers of \(G\) and its complement in terms of \(n\). The \emph{edge cost} \(ec(G)\) of a graph \(G\) is a parameter connected with node fault tolerance studies in computer science. Here we obtain bounds for the sum and product of the edge cost of a graph and its complement, analogous to the theorem of Nordhaus and Gaddum.

In this paper we obtain some results on orthogonal arrays \((O-arrays)\) of strength six by considering balanced arrays \((B-arrays)\) of strength six with \(\underline{\mu}’ = (\mu – 1, \mu, \mu, \mu, \mu, \mu, \mu – 1)\) which we call Near O-arrays. As a consequence we demonstrate that we obtain better bounds on the number of constraints for some O-arrays as compared to those given by Rao (1947).

Let \([n, k, d; q]\)-codes be linear codes of length \(n\), dimension \(k\) and minimum Hamming distance \(d\) over \({GF}(q)\). Let \(d_7(n, k)\) be the maximum possible minimum Hamming distance of a linear \([n, k, d; 7]\)-code for given values of \(n\) and \(k\). In this paper, fifty-eight new linear codes over \({GF}(7)\) are constructed, the nonexistence of sixteen linear codes is proved and a table of \(d_7(n,k)\) , \(k\leq7\), \(n\leq100\) is presented.

We study problems related to the number of edges of a graph with diameter constraints. We show that the problem of finding, in a graph of diameter \(k \geq 2\), a spanning subgraph of diameter \(k\) with the minimum number of edges is NP-hard. In addition, we propose some efficient heuristic algorithms for solving this problem. We also investigate the number of edges in a critical graph of diameter 2. We collect some evidence which supports our conjecture that the number of edges in a critical graph of diameter 2 is at most \(\Delta(n-\Delta)\) where \(\Delta\) is the maximum degree. In particular, we show that our conjecture is true for \(\Delta \leq \frac{1}{2}n\) or \(\Delta \geq n-5\).

A digraph \(D\) is reversible if it is isomorphic to the digraph obtained by reversing all arcs of \(D\). A digraph is subreversible if adding any arc between two non-adjacent vertices results in a reversible digraph. We characterize all subreversible digraphs which do not contain cycles of length \(3\) or \(4\).

In this paper we prove that, except for the 4-cycle and the 5-cycle, every 2-connected \(K(1,3)\)-free graph of diameter at most two is pancyclic.

The well-known clique tree representation for chordal graphs is extended to multidimensional representations for arbitrary graphs in which the number of vertices in the representation, minus the number of edges, plus the number of distinguished cycles, minus the number of distinguished polyhedra, and so on, always equals one. This approach generalizes both chordal graphs and cycle spaces of graphs. It also leads to a `dimension’ parameter that is shown to be no greater than the boxicity, chromatic number, and tree-width parameters.

An \(e=1\) function is a function \(f: V(G) \rightarrow [0,1]\) such that every non-isolated vertex \(u\) is adjacent to some vertex \(v\) such that \(f(u) + f(v) = 1\), and every isolated vertex \(w\) has \(f(w) = 1\). A theory of \(e=1\) functions is developed focussing on minimal and maximal \(e=1\) functions. Relationships are traced between \(e=1\) parameters and some well-known domination parameters, which lead to results about classical and fractional domination parameters.

We formulate the construction of 1-rotational difference families as a combinatorial optimization problem. A tabu search algorithm is used to find an optimal solution to the optimization problem for various 1-rotational difference family parameters. In particular, we construct two new 1-rotational difference families which lead to an equal number of new 1-rotational RBIBDs with parameters: \((36, 9, 8)\) and \((40, 10, 9)\). Our algorithm also was able to construct six non-isomorphic \((36, 9, 8)\) and three \((40, 10, 9)\) RBIBDs

For two vertices \(u\)  and \(v\) of a connected graph \(G\) , the set \(H(u,v)\) consists of all those vertices lying on a \(u-v\) geodesic in \(G\) . Given a set \(S\) of vertices of \(G\) , the union of all sets \(H(u,v)\) for \(u,v\in S\) is denoted by \(H(S)\) . A convex set \(S\) satisfies \(H(S)=S\) . The convex hull \([S]\) is the smallest convex set containing \(S\) . The hull number \(h(G)\) is the minimum cardinality among the subsets \(S\) of \(V(G)\) with \([S]=V(G)\) . A set \(S\) is a geodetic set if \(H(S)=V(G)\) ; while \(S\) is a hull set if \([S]=V(G)\) . The minimum cardinality of a geodetic set of \(G\) is the geodetic number \(g(G)\) . A subset \(T\) of a minimum hull set \(S\) is called a forcing subset for \(S\) if \(S\) is the unique minimum hull set containing \(T\) . The forcing hull number \(f(S,h)\) of \(S\) is the minimum cardinality among the forcing subsets of \(S\) , and the forcing hull number \(f(G,h)\) of \(G\) is the minimum forcing hull number among all minimum hull sets of \(G\) . The forcing geodetic number \(f(S,g)\)  of a minimum geodetic set \(S\) in \(G\) and the forcing geodetic number \(f(G,g)\) of \(G\) are defined in a similar fashion. The forcing hull numbers of several classes of graphs are determined. It is shown that for integers \(a,b\) with \(0\leq a\leq b\) , there exists a connected graph \(G\) such that \(f(G,h)=a\) and \(h(G)=b\) . We investigate the realizability of integers \(a,b\geq0\) that are the forcing hull and forcing geodetic numbers, respectively, of some graph.