For a graph facility or multi-facility location problem, each vertex is typically considered to be the location for one customer or one facility. Typically, the number of facilities is predetermined, and one must optimally locate these facilities so as to minimize some function of the distances between customers and facilities (and, perhaps, of the distances among the facilities). For example, p facility locations (such as, for hospitals or fire stations) might be chosen so as to minimize the maximum or the average distance from a customer to the nearest facility. The problem investigated in this paper considers all of the facilities to be distinct, and we seek to minimize the average customer-to-facility distance, primarily for grid graphs.

Let \(G = (V, E)\) be a graph.A set \(S \subseteq V\) is a dominating set if every vertex not in \(S\) is adjacent to a vertex in \(S\).The domination number of \(G\), denoted by \(\gamma(G)\), is the minimum cardinality of a dominating set of \(G\).Sanchis [8] showed that a connected graph \(G\) of size \(q\) and minimum degree at least \(2\) has domination number at most \((q+2)/3\).
In this paper, connected graphs \(G\) of size \(q\) with minimum degree at least \(2\) satisfying \(\gamma(G) > \frac{q}{3}\) are characterized.

For two vertices \(u\) and \(v\) in a strong oriented graph \(D\) of order \(n \geq 3\), the strong distance \(\text{sd}(u,v)\) between \(u\) and \(v\) is the minimum size of a strong subdigraph of \(D\) containing \(u\) and \(v\). For a vertex \(v\) of \(D\), the strong eccentricity \(\text{se}(v)\) is the strong distance between \(v\) and a vertex farthest from \(v\). The minimum strong eccentricity among the vertices of \(D\) is the strong radius \(\text{srad}(D)\), and the maximum strong eccentricity is its strong diameter \(\text{sdiam}(D)\). It is shown that every pair \(r,d\) of integers with \(3 \leq r \leq d \leq 2r\) is realizable as the strong radius and strong diameter of some strong oriented graph.Moreover, for every strong oriented graph \(D\) of order \(n \geq 3\), it is shown that\(\text{sdiam}(D) \leq \left\lfloor \frac{5(n-1)}{3} \right\rfloor.\)Furthermore, for every integer \(n \geq 3\), there exists a strong oriented graph \(D\) of order \(n\) such that \(\text{sdiam}(D) = \left\lfloor \frac{5(n-1)}{3} \right\rfloor.\)

For each vertex \(s\) of the subset \(S\) of vertices of a graph \(G\), we define Boolean variables \(p\), \(q\), \(r\) which measure the existence of three kinds of \(S\)-private neighbors (\(S\)-pns) of \(s\). A \(3\)-variable Boolean function \(f = f(p, q, r)\) may be considered as a compound existence property of \(S\)-pns. The set \(S\) is called an \(f\)-set of \(G\) if \(f = 1\) for all \(s \in S\), and the class of all \(f\)-sets of \(G\) is denoted by \(\Omega_f\). Special cases of \(\Omega_f\) include the
independent sets, irredundant sets, open irredundant sets, and CO-irredundant sets of \(G\).
There are \(62\) non-trivial families \(\Omega_f\) which include the \(7\) families of a framework proposed earlier by Fellows, Fricke, Hedetniemi, and Jacobs. The functions \(f\) for which \(\Omega_f\) is hereditary for any graph \(G\) are determined. Additionally, the existence and properties of \(f\)-Ramsey numbers (analogues of the elusive classical Ramsey numbers) are investigated, and future directions for the theory of the classes \(\Omega_f\) are considered.

The edge-integrity of a graph \(G\) is given by\(\min\limits_{S\subseteq E(G)} \{ |S| + m(G – S) \},\)where \(m(G – S)\) denotes the maximum order of a component of \(G – S\).
Let \(I'(G)\) denote the edge-integrity of a graph \(G\). We define a graph \(G\) to be \(I’\)-maximal if for every edge \(e\) in \(\overline{G}\), the complement of graph \(G\), \(I'(G + e) > I'(G)\). In this paper, some basic results of \(I’\)-maximal graphs are established, the girth of a connected \(I’\)-maximal graph is given and lower and upper bounds on the size of \(I’\)-maximal connected graphs with given order and edge-integrity are investigated. The \(I’\)-maximal trees and unicyclic graphs are completely characterized.

The numbers of sets of independent edge sets in \(2\)-lattice graphs, wheel graphs, and circuit graphs are computed.

It is well-known that if \(D\) is any finite set of integers, then there is an \(n\) large enough so that there exists a 2-coloring of the positive integers that avoids any monochromatic \(n\)-term arithmetic progressions whose common differences belong to \(D\).If \(\vec{d} = (d_1, \ldots, d_k)\) and \(\vec{n} = (n_1, \ldots, n_k)\) are \(k\)-tuples of positive integers, denote by \(f_{\vec{d}}(\vec{n})\) the least positive integer \(N\), if it exists, such that for every 2-coloring of \([1, N]\) there is, for some \(i\), a monochromatic \(n_i\)-term arithmetic progression with common difference \(d_i\).This paper looks at the problem of determining when \(f_{\vec{d}}(\vec{n})\) exists, and its value when it does exist, for \(k \leq 3\).A complete answer is given for \(k = 2\).A partial answer is given for \(k = 3\), including the fact that for all ordered triples \(\vec{d}\), \(f_{\vec{d}}(4, 4, 4)\) does not exist.

Given a set of \(N\) cities, construct a connected network which has minimum length. The problem is simple enough, but the catch is that you are allowed to add junctions in your network. Therefore, the problem becomes how many extra junctions should be added, and where should they be placed so as to minimize the overall network length.This intriguing optimization problem is known as the Steiner Minimal Tree Problem (SMT), where the junctions that are added to the network are called Steiner Points.The focus of this paper is twofold.First We look at the computational history of the problem, up through and including a new method to compute SMT’s in parallel.Secondly We look at future work in the computation of Steiner Minimal Trees.

Suppose \(S\) is a defining set of a symmetric \(2\)-( \(v, k, \lambda\) ) design \(D\), where \(\lambda = 1\) or \(2\); that is, \(D\) is a projective plane or a biplane.In this paper, conditions under which the residual of \(S\) is a defining set of the residual of \(D\) are investigated.As a consequence, inequalities relating the sizes of smallest defining sets of \(D\) and of the residual of \(D\) are obtained.The exact sizes of smallest defining sets of \({PG}(2, 5)\), \({AG}(2, 5)\), and the three non-isomorphic \(2\)-( \(10, 4, 2\) ) designs are determined.

Exact designs with \(n\) observations and \(k\) two-level factors in the presence of autocorrelated errors are considered. The problem of finding \(D\)- and \(A\)- optimal designs is discussed. An algorithm for constructing such designs, using exhaustive search for different values of \(n\) and \(k\), is developed. The application of this algorithm showed that, in the case of positive autocorrelation, the maximum possible number of interchanges of the factor levels provides almost optimal designs.On the contrary, in the case of negative autocorrelation, the minimum such number provides almost optimal designs. A list of the exact \(D\)- and \(A\)-optimal designs is given.