Using a linear space on \(v\) points with all block sizes \(|B| \equiv 0\) or \(1 \pmod{3}\), Doyen and Wilson construct a Steiner triple system on \(2v+1\) points that embeds a Steiner triple system on \(2|B|+1\) points for each block \(B\). We generalise this result to show that if the linear space on \(v\) points is extendable in a suitable way, there is a Steiner quadruple system on \(2v+2\) points that embeds a Steiner quadruple system on \(2(|B|+1)\) points for each block \(B\).

A graph with a graceful labeling (an \(\alpha\)-labeling) is called a graceful (\(\lambda\)-graceful) graph. In this paper, six methods for constructing bigger graceful graphs from a given graceful graph or a set of given \(\lambda\)-graceful graphs are provided. Two of which generalize Koh and others’ Theorems in [2, 3].

Let \(B_2\) be the bananas surface arising from the torus by contracting two different meridians of the torus to a simple point each. It was proved in [8] that there is not a finite Kuratowski theorem for \(B_2\).

A graph is outer-bananas-surface if it can be embedded in \(B_2\) so that all its vertices lie on the same face. In this paper, we prove that the class of the outer-\(B_2\) graphs is closed under minors. In fact, we give the complete set of \(38\) minor-minimal non-outer-\(B_2\) graphs and we also characterize these graphs by a finite list of forbidden topological minors.

We also extend outer embeddings to other pseudosurfaces. The \(S\) pseudosurfaces treated are spheres joined by points in such a way that each sphere has two singular points. We give an excluded minor characterization of outer-\(S\) graphs and we also give an explicit and finite list of forbidden topological minors for these pseudosurfaces.

We show that several known theorems on graphs and digraphs are equivalent. The list of equivalent theorems include Kotzig’s result on graphs with unique \(1\)-factors, a lemma by Seymour and Giles, theorems on alternating cycles in edge-colored graphs, and a theorem on semicycles in digraphs.

We consider computational problems related to the quoted results; all these problems ask whether a given (di)graph contains a cycle satisfying certain properties which runs through \(p\) prescribed vertices. We show that all considered problems can be solved in polynomial time for \(p < 2\) but are NP-complete for \(p \geq 2\).

We define a new graph operation called “dissolve \(N(v)\) into \(v\)” where \(N(v)\) is the set of vertices adjacent to a vertex \(v\) and characterize odd cycles of length greater than \(5\) in terms of \(p\)-critical graphs using this operation. This enables us to re-phrase the Strong Perfect Graph Conjecture,

Gray and Ramsay [5] showed that for any \(s \geq (2t – 1)2^t\), a \(t-(v,k)\) trade of volume \(s\) exists. In this note we improve their bound and show that for \(t \geq 3\), a given \(k\), and \(s \geq (t – 2)2^t + 2^{t-1} + 2\), there exists a simple \(t-(v,k)\) trade of volume \(s\).

\[S_{(p,x)} = \sum\limits_{k=0}^{n} {\binom{n}{k}}^p x^k\]

where \(n \geq 0\).

Then it is well-known that \(S_n(1,x), S_2(2,1), S_n(3,1)\) and \(S_n(3,1)\) can be exhibited in closed form. The formula

\[S_{2n}{(3,-1)} = (-1)^n\binom{2n}{n}\binom{3n}{n}\]

was discovered by A. C. Dixon in \(1891\). L. Carlitz [Mathematics Magazine, Vol. \(32 (1958), 47-48]\) posed the formulas

\[S_n{(3,1)}= ((x^n))(1-x^2)^nP_n(\frac{1+x}{1-x})\]

and

\[S_n{(4,1)} = ((x^n))(1-x)^{2n}\{P_n(\frac{1+x}{1-x})\}\]

where \(((x^n))f(x)\) means the coefficient of \(x^n\) in the series expansion of \(f(x)\). We use Legendre polynomials to get the analogous formulas

\[S_n{(3,-1)} = ((x^n))(1_x)^{2n}\]

and

\[S_n{(5,1)} = ((x^n))(1_x)^{2n}P_n(\frac{1+x}{1-x}S_n(3,x)\]

We obtain some partial results for \(S_n(p,x)\) when \(p\) is arbitrary, and also give a new proof of Dixon’s formula.

A graph \(H\) of order \(n\) is said to be embeddable in a graph \(G\) of order \(n\), if \(G\) contains a spanning subgraph isomorphic to \(H\). It is well known that any non-star tree \(T\) of order \(n\) is embeddable in its complement (i.e. in \(K_n – E(T)\)). In the paper “Packing two copies of a tree into its fourth power” by Hamamache Kheddouci, Jean-Francois Saclé, and Mariusz Wodgniak, Discrete Mathematics 213 (2000), 169-178, it is proved that any non-star tree \(T\) is embeddable in \(T^4 – E(T)\). They asked whether every non-star tree \(T\) is embeddable in \(T^3 – E(T)\). In this paper, answering their question negatively, we show that there exist trees \(T\) such that \(T\) is not embeddable in \(T^3 – E(T)\).

The linear \(2\)-arboricity \(la_2(G)\) of a graph \(G\) is the least integer \(k\) such that \(G\) can be partitioned into \(k\) edge-disjoint forests, whose component trees are paths of length at most \(2\). We prove that \(la_2(G) \leq \lfloor \frac{\Delta(G) + 4}{2} \rfloor\) if \(G\) is an outerplanar graph with maximum degree \(\Delta(G)\).

A paired-dominating set of a graph \(G\) is a dominating set of vertices whose induced subgraph has a perfect matching. We characterize the trees having unique minimum paired-dominating sets.