For given edges \(e_1, e_2 \in E(G)\), a spanning trail of \(G\) with \(e_1\) as the first edge and \(e_2\) as the last edge is called a spanning \((e_1, e_2)\)-trail. In this note, we consider best possible degree conditions to assure the existence of these trails for every pair of edges in a \(3\)-edge-connected graph \(G\).

In this paper, it is proved that an abelian \((351, 126, 45)\)-difference set only exists in the groups with exponent \(39\). This fills two missing entries in Lopez and Sanchez’s table with answer “no”. Furthermore, if a Spence difference set \(D\) has Character Divisibility Property, then \(D\) is one of the difference sets constructed by Spence.

In this paper we concentrate on those graphs which are \((a, d)\)-face antimagic, and we show that the graphs \(D_n\) from a special class of convex polytopes consisting of \(4\)-sided faces are \((6n + 3, 2)\)-face antimagic and \((4n + 4, 4)\)-face antimagic. It is worth a conjecture, we feel, that \(D_n\) are \((2n + 5, 6)\)-face antimagic.

Let \(\{G(n,k)\}\) be a family of graphs where \(G(n, k)\) is the graph obtained from \(K_n\), the complete graph on \(n\) vertices, by removing any set of \(k\) parallel edges. In this paper, the lower bound for the multiplicity of triangles in any \(2\)-edge coloring of the family of graphs \(\{G(n, k)\}\) is calculated and it is proved that this lower bound is sharp when \(n \geq 2k + 4\) by explicit coloring schemes in a recursive manner. For the cases \(n = 2k + 1, 2k + 2\), and \(2k + 3\), this lower bound is not sharp and the exact bound in these cases are also independently calculated by explicit constructions.

In this paper we introduce a new parameter related to the index of convergence of Boolean matrices — the generalized index. The parameter is motivated by memoryless communication systems. We obtain the values of this parameter for reducible, irreducible and symmetric matrices.

In this paper we extend the definition of pseudograceful graphs given by Frucht [3] to all graphs \(G\) with vertex set \(V(G)\) and edge set \(E(G)\) such that
\(|V(G)| \leq |E(G)| + 1\) and we prove that if \(G\) is a pseudograceful graph, then \(G \cup K_{m,n}\).is pseudograceful
for \(m,n \geq 2\) and \((m,n) \neq (2,2)\) and is graceful for \(m,n \geq 2\). This enables us to obtain several new families of graceful and disconnected graphs.

A graph \(G\) is \(Z_m\)-well-covered if \(|I| \equiv |J| \pmod{m}\), for all \(I\), \(J\) maximal independent sets in \(V(G)\). A graph \(G\) is a \(1-Z_m\)-well-covered graph if \(G\) is \(Z_m\)-well-covered and \(G\setminus\{v\}\) is \(Z_m\)-well-covered, \(\forall v \in V(G)\). A graph \(G\) is strongly \(Z_m\)-well-covered if \(G\) is a \(Z_m\)-well-covered graph and \(G\setminus\{e\}\) is \(Z_m\)-well-covered, \(\forall e \in E(G)\). Here we prove some results about \(1-Z_m\)-well-covered and strongly \(Z_m\)-well-covered graphs.

There are two types of quadrangles in a projective plane, Fano quadrangles, and non-Fano quadrangles. The number of quadrangles in some small projective planes is counted according to type, and an interesting configuration in the Hughes plane is displayed.

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.

Maximal partial spreads of the sizes \(13, 14, 15, \ldots, 22\) and \(26\) are described. They were found by using a computer. The computer also made a complete search for maximal partial spreads of size less than or equal to \(12\). No such maximal partial spreads were found.

Suppose we are given a set of sticks of various integer lengths, and that we have a knife that can cut as many as \(w\) sticks at a time. We wish to cut all the sticks up into pieces of unit length. By what procedure should the sticks be cut so that the total number of steps required is minimum? In this paper we show that the following natural algorithm is optimal: at each stage, choose the \(w\) longest sticks (or all sticks of length \(> 1\) if there are fewer than \(w\) of them) and cut them all in half (or as nearly in half as possible).

In this paper, we study intersection assignments of graphs using multiple intervals for each vertex, where each interval is of identical length or in which no interval is properly contained in another. The resulting parameters unit interval number, \(i_u(G)\) and proper interval number, \(i_p(G)\) are shown to be equal for any graph \(G\). Also, \(i_u(G)\) of a triangle-free graph \(G\) with maximum degree \(D\) is \(\left\lceil\frac{D+1}{2}\right\rceil\) if \(G\) is regular and \(\left\lceil\frac{D}{2}\right\rceil\) otherwise.

In [3] Brualdi and Hollingsworth conjectured that for any one-factorization \(\mathcal{F}\) of \(K_n\), there exists a decomposition of \(K_{2n}\) into spanning trees orthogonal to \(\mathcal{F}\). They also showed that two such spanning trees always existed. We construct three such trees and exhibit an infinite class of complete graphs with an orthogonal decomposition into spanning trees with respect to the one-factorization \(GK_{2n}\).

Four generalized theorems involving partitions and \((n+1)\)-color partitions are proved combinatorially. Each of these theorems gives us infinitely many partition identities. We obtain new generating functions for \(F\)-partitions and discuss some particular cases which provide elegant Rogers-Ramanujan type identities for \(F\)-partitions.

The aim of this paper is to study the isoperimetric numbers of double coverings of a complete graph. It turns out that these numbers are very closely related to the bisection widths of the double coverings and the degrees of unbalance of the signed graphs which derive the double coverings. For example, the bisection width of a double covering of a complete graph \(K_m\) is equal to \(m\) times its isoperimetric number. We determine which numbers can be the isoperimetric numbers of double coverings of a complete graph.

A digraph operation called pushing a set of vertices is studied with respect to tournaments. When a set \(X\) of vertices is pushed, the orientation of every arc with exactly one end in \(X\) is reversed. We discuss the problems of which tournaments can be made transitive and which can be made isomorphic to their converse using this operation.

Let \(I(G)\) be a graphical invariant defined for any graph \(G\). For several choices of \(I\) representing domination parameters, we characterize sequences of positive integers \(a_1,a_2,\ldots,a_n\) which have an associated sequence of graphs \(G_1,G_2,\ldots,G_n\) such that \(G_i\) has \(i\) vertices, \(G_i\) is an induced subgraph of \(G_{i+1}\), and \(I(G_i) = a_i\).

The fine structure of a directed triple system of index \(\lambda\) is the vector \((c_1,c_2,\ldots,c_\lambda)\), where \(c_i\) is the number of directed triples appearing precisely \(i\) times in the system. We determine necessary and sufficient conditions for a vector to be the fine structure of a directed triple system of index \(3\) for \(v \equiv 2 \pmod{3}\).