Let \(G\) be a connected \((p,q)\)-graph. Let \(\gamma_c\) denote the connected domination number of \(G\). In this paper, we prove that \(q\leq \lfloor\frac{p(p-\gamma_c)}{2}\rfloor\) and equality holds if and only if \(G = C_p\) or \(K_p\) or \(K_p – Q\) where \(Q\) is a minimum edge cover of \(K_p\). We obtain similar bounds on \(\gamma_q\) for graphs with given: Total domination number \(\gamma_t\) Clique domination number \(\gamma_k\) Edge domination number \(\gamma ‘\) Connected edge domination number \(\gamma’_{c }\) and for each of these parameters, characterize the class of graphs attaining the corresponding bound.

We consider all \(2-(v,3)\) trades in which every pair appears at most once in each part of the trade, and we call them Steiner Triple Trades \({STT}(v)\). We completely classify \({STT}(v)\) with \(6 \leq vol(T) \leq 9\).

Let \(G\) be a graph. A function \(f: V(G) \to \{1, 2, \ldots, k\}\) is a \(k\)-ranking for \(G\) if \(f(u) = f(v)\) implies that every \(u-v\) path \(P\) contains a vertex \(w\) such that \(f(w) > f(u)\). A function \(f: V(G) \to \{1, 2, \ldots, 4\}\) is a minimal \(k\)-ranking if \(f\) is a \(k\)-ranking and for any \(x\) such that \(f(x) > 1\) the function \(g(z) = f(z)\) for \(z \neq x\) and \(1 \leq g(x) < f(x)\) is not a \(k\)-ranking. This paper establishes further properties of minimal rankings, gives a procedure for constructing minimal rankings, and determines, for some classes of graphs, the minimum value and maximum value of \(k\) for which \(G\) has a minimal \(k\)-ranking. In addition, we establish tighter bounds for the minimum value of \(k\) for which \(G\) has a \(k\)-ranking.

A tournament is a complete directed graph. A convex subset is a vertex subset with the property that every two-path beginning and ending inside the convex subset is contained completely within the subset. This paper shows a relationship between convex subsets and transitive closures which leads to an optimal \(O(n^3)\)-time algorithm for finding all convex subsets in a tournament.

Let \({A}(n,3)\) denote the \(n\)-dimensional affine space over the finite field of order three. In this paper, we use basic combinatorial principles to discuss some old and new results about the lines in \({A}(3,3)\). For \(S \subset {A}(3,3)\), let \(||S||_3\) and \(||S||_{3,k}\) respectively denote the number of lines and the number of \(k\)-lines of \({A}(3,3)\) contained entirely in \(S\). For each \(t\), we compute \(\alpha_3(t) = \min\{||S||_3 : |S| = t\}\) and \(\Omega_3(t) = \max\{||S||_3 : |S| = t\}\). We also give results about \(\alpha_{3,k}(t) = \min\{||S||_{n,k} : |S| = t\}\) and \(\omega_{3,k}(t) = \max\{||S||_{n,k} : |S| = t\}\) and results about \(1\)-lines and \(n\)-lines in \({A}(n,3)\).

The binary linear code of a Steiner triple system on \(2^d – 1\) points, where \(d \geq 3\) is an integer, contains a copy of the Hamming code \(\mathcal{H}_{di}\) this fact can be used to characterize those systems on \(2^d – 1\) points that have low dimension, and to show that these systems can always be extended to Steiner quadruple systems whose binary code is the extended code of the Steiner triple system.

Let \(m\) and \(n\) be positive integers, and let \(\mathbf{R} = (r_1, \ldots, r_m)\) and \(\mathbf{S} = (s_1, \ldots, s_n)\) be nonnegative integral vectors with \(r_1 + \cdots + r_m = s_1 + \cdots + s_n\). Let \(\mathbf{Q} = (q_{ij})\) be an \(m \times n\) nonnegative integral matrix. Denote by \(\mathcal{U}^Q(\mathbf{R}, \mathbf{S})\) the class of all \(m \times n\) nonnegative integral matrices \(\mathbf{A} = (a_{ij})\) with row sum vector \(\mathbf{R}\) and column sum vector \(\mathbf{S}\) such that \(a_{ij} \leq q_{ij}\) for all \(i\) and \(j\). We study a condition for the existence of a matrix in \(\mathcal{U}^Q(\mathbf{R}, \mathbf{S})\). The well known existence theorem follows from the max-flow-min-cut theorem. It contains an exponential number of inequalities. By generalizing the Gale-Ryser theorem, we obtain some conditions under which this exponential number of inequalities can be reduced to a polynomial number of inequalities. We build a kind of hierarchy of theorems: under weaker and weaker conditions, a (larger and larger) polynomial (in \(n\)) number of inequalities yield a necessary and sufficient condition for the existence of a matrix in \(\mathcal{U}^Q(\mathbf{R}, \mathbf{S})\).

Let \(G = (V, E)\) be a graph and let \(\mathcal{H}\) be a set of graphs. A set \(S \subseteq V\) is \(\mathcal{H}\)-independent if for all \(H \in \mathcal{H}\), \(\langle S \rangle\) contains no subgraph isomorphic to \(H\). A set \(S \subseteq V\) is an \(\mathcal{H}\)-dominating set of \(G\) if for every \(v \in V – S\), \(\langle S \cup \{v\} \rangle\) contains a subgraph containing \(v\) which is isomorphic to some \(H \in \mathcal{H}\).

The \(\mathcal{H}\)-domination number of a graph \(G\), denoted by \(\gamma_{\mathcal{H}}(G)\), is the minimum cardinality of an \(\mathcal{H}\)-dominating set of \(G\) and the \(\mathcal{H}\)-independent domination number of \(G\), denoted by \(i_{\mathcal{H}}(G)\), is the smallest cardinality of an \(\mathcal{H}\)-independent \(\mathcal{H}\)-dominating set of \(G\).

A sequence of positive integers \(a_2 \leq \cdots \leq a_m\) is said to be a domination sequence if there exists a graph \(G\) such that \(\gamma_{(K_k)}(G) = a_k\) for \(k = 2, \ldots, m\). In this paper, we find an upper bound for \(\gamma_{\mathcal{H}}(G)\) and show that the problems of computing \(\gamma_{\{K_n\}}\) and \(i_{\{K_n\}}\) are NP-hard. Finally, we characterize nondecreasing sequences of positive integers which are domination sequences, and provide a sufficient condition for equality of \(\gamma_{\{K_n\}}(G)\) and \(i_{\{K_n\}}(G)\).

In this paper, we prove that the partial sums of the chromatic polynomial of a graph define an alternating sequence of upper and lower bounds.

Let \(H\) be a fixed graph without isolated vertices, and let \(G\) be a graph on \(n\) vertices. Let \(2 \leq k \leq n-1\) be an integer. We prove that if \(k \leq n-2\) and every \(k\)-vertex induced subgraph of \(G\) is \(H\)-decomposable, then \(G\) or its complement is either a complete graph or a complete bipartite graph. This also holds for \(k = n-1\) if all the degrees of the vertices of \(H\) have a common factor. On the other hand, we show that there are graphs \(H\) for which it is NP-Complete to decide if every \(n-1\)-vertex subgraph of \(G\) is \(H\)-decomposable. In particular, we show that \(H = K_{1,h-1}\), where \(h > 3\), are such graphs.