Let \(S = T \sim (\cup\{A : A \in \mathcal{A}\})\), where \(T\) is a simply connected orthogonal polygon and \(\mathcal{A}\) is a collection of \(n\) pairwise disjoint open rectangular regions contained in \(T\). Point \(x\) belongs to the staircase kernel of \(S\), Ker \(S\), if and only if \(x\) belongs to Ker \(T\) and neither the horizontal nor the vertical line through \(x\) meets any \(A\) in \(\mathcal{A}\). This produces a Krasnosel’skii-type theorem for \(S\) in terms of \(n\). However, an example shows that, independent of \(n\), no general Krasnosel’skii number exists for \(S\).

We show that the secants of an arc of size near to \({\sqrt{2q}}\) cover almost half plane; also, a random union of \(log_2 q\) arcs of this size is such that its secants cover the plane.

Generalized Steiner triple systems, \(GS(2,3,n,g)\) are used to construct maximum constant weight codes over an alphabet of size \(g+1\) with distance \(3\) and weight \(3\) in which each codeword has length \(n\). The existence of \(GS(2,3,n,g)\) has been solved for \(g = 2,3,4,5,6,9\). The necessary conditions for the existence of a \(GS(2,3,n,g)\) are \((n-1)g \equiv 0 \pmod{2}\), \(n(n-1)g \equiv 0 \pmod{6}\), and \(n \geq g+2\). In this paper, the existence of a \(GS(2,3,7,g)\) for any given \(g \geq 7\) is investigated. It is proved that if there exists a \(GS(2,3,n,g)\) for all \(n\), \(g+2 \leq n \leq 9g+158\), satisfying the two congruences, then the necessary conditions are also sufficient. As an application it is proved that the necessary conditions for the existence of a \(GS(2,3,n,g)\) are also sufficient for \(g = 7,8\).

The Ramsey numbers \(r(C_5,G)\) are determined for all graphs \(G\) of order six.

For a graph \(G\), let \(Var(G)\) denote the variance of the degree sequence of \(G\), let \(sq(G)\) denote the sum of the squares of the degrees of \(G\), and let \(t(G)\) denote the number of triangles in \(G\) and in its complement. The parameters are related by:
\(Var(G) = \frac{sq(G)}{n} – d^2\)
where \(d\) is the average degree of \(G\), and
\(t(G) = \binom{n}{3} + \frac{sq(G)}{2} – {m(n-1)}\)
Let \(Var(n)\) denote the maximum possible value of \(Var(G)\) where \(G\) has \(n\) vertices, and let \(sq(n,m)\) and \(t(n,m)\) denote the maximum possible values of \(sq(G)\) and \(t(G)\), respectively, where \(G\) has \(n\) vertices and \(m\) edges. We present a polynomial time algorithm which generates all the graphs with \(n\) vertices and \(m\) edges having \(sq(G) = sq(n,m)\) and \(t(G) = t(n,m)\). This extends a result of Olpp which determined \(t(n,m)\). We also determine \(Var(n)\) precisely for every \(n\), and show that
\[ Var(n) = \frac{q(q-1)^2}{n}(1-\frac{q}{n}) =\frac{27}{256}n^2=O(n)\]
where \(q = [\frac{3n}{4}] \),(if \(n \equiv 2 \pmod 4\) the rounding is up ) thereby improving upon previous results.

This paper defines a new graph invariant by considering the set of connected induced subgraphs of a graph and defining a polynomial whose coefficients are determined by this partially ordered set of subgraphs. We compute the polynomial for a variety of graphs and also determine the effects on the polynomial of various graph operations.

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)\). When \(H(S) = V(G)\), we call \(S\) a geodetic set. The minimum cardinality of a geodetic set is the geodetic number \(g(G)\). It is shown that every two integers \(a\) and \(b\) with \(2 \leq a \leq b\) are realizable as the hull and geodetic numbers, respectively, of some graph. For every nontrivial connected graph \(G\), we find that \(h(G) = h(G \times K_2)\). A graph \(F\) is a minimum hull subgraph if there exists a graph \(G\) containing \(F\) as induced subgraph such that \(V(F)\) is a minimum hull set for \(G\). Minimum hull subgraphs are characterized.

For a graph \(G = (V, E)\), a set \(S \subseteq V\) is a dominating set if every vertex in \(V – S\) is adjacent to at least one vertex in \(S\). A dominating set \(S \subseteq V\) is a paired-dominating set if the induced subgraph \(\langle S\rangle\) has a perfect matching. We introduce a variant of paired-domination where an additional restriction is placed on the induced subgraph \(\langle S\rangle \). A paired-dominating set \(S\) is an induced-paired dominating set if the edges of the matching are the induced edges of \(\langle S\rangle\), that is, \(\langle S\rangle\) is a set of independent edges. The minimum cardinality of an induced-paired dominating set of \(G\) is the induced-paired domination number \(\gamma_{ip}(G)\). Every graph without isolates has a paired-dominating set, but not all these graphs have an induced-paired dominating set. We show that the decision problem associated with induced-paired domination is NP-complete even when restricted to bipartite graphs and give bounds on \(\gamma_{ip}(G)\). A characterization of those triples \((a, b, c)\) of positive integers \(a \leq b \leq c\) for which a graph has domination number \(a\), paired-domination number \(b\), and induced-paired domination \(c\) is given. In addition, we characterize the cycles and trees that have induced-paired dominating sets.

Let \(M\) be an \(m\)-subset of \(\mathrm{PG}(k, 2)\), the finite projective geometry of dimension \(k\) over \(\mathrm{GF}(2)\). We would like to know the maximum number of lines that can be contained in \(M\). In this paper, we will not only give the maximum number of lines contained in \(m\)-subsets of \(\mathrm{PG}(k,2)\), but also construct an \(m\)-subset of \(\mathrm{PG}(k,2)\) containing the maximum number of lines.