In this paper, we look at generalizations of Stirling numbers which arise for arbitrary integer sequences and their \(k\)-th powers. This can be seen as a complementary strategy to the unified approach suggested in [9]. The investigations of [3] and [14] present a more algebraically oriented approach to generalized Stirling numbers.

In the first and second sections of the paper, we give the corresponding formulas for the generalized Stirling numbers of the second and first kind, respectively. In the third section, we briefly discuss some examples and special cases, and in the last section, we apply the square case to facilitate a counting approach for set partitions of even size.

In this paper, we give two sufficient conditions for a graph to be type \(1\) with respect to the total chromatic number and prove the following results:

(i) If \(G\) and \(H\) are of type \(1\), then \(G \times H\) is of type \(1\);

(ii) If \(\varepsilon(G) \leq v(G) + \frac{3}{2}\Delta(G) – 4\), then \(G\) is of type \(1\).

We prove several results dealing with various counting functions for partitions of an integer into four squares of equal parity. Some are easy consequences of earlier work, but two are new and surprising. That is, we show that the number of partitions of \(72n+ 60\) into four odd squares (distinct or not) is even.

We prove that if \(G\) is a simple graph of order \(n \geq 3k\) such that \(|N(x) \cup N(y)| \geq 3k\) for all nonadjacent pairs of vertices \(x\) and \(y\), then \(G\) contains \(k\) vertex-independent cycles.

The non-planar vertex deletion or vertex deletion \(vd(G)\) of a graph \(G = (V, E)\) is the smallest non-negative integer \(k\) such that the removal of \(k\) vertices from \(G\) produces a planar graph. Hence, the maximum planar induced subgraph of \(G\) has precisely \(|V| – vd(G)\) vertices. The problem of computing vertex deletion is in general very hard; it is NP-complete. In this paper, we compute the non-planar vertex deletion for the family of toroidal graphs \(C_n \times C_m\).

Let \(K_4\backslash e=…\). If we remove the “diagonal” edge, the result is a \(4\)-cycle. Let \((X,B)\) be a \(K_4\backslash e\) design of order \(n\); i.e., an edge-disjoint decomposition of \(K_n\) into copies of \(K_4\backslash e\). Let \(D(B)\) be the collection of “diagonals” removed from the graphs in \(B\) and \(C(B)\) the resulting collection of \(4\)-cycles. If \(C_2(B)\) is a reassembly of these edges into \(4\)-cycles and \(L\) is the collection of edges in \(D(B)\) not used in a \(4\)-cycle of \(C_2(B)\), then \((X, (C_1(B) \cup C_2(B)), L)\) is a packing of \(K_n\) with \(4\)-cycles and is called a metamorphosis of \((X,B)\). We construct, for every \(n = 0\) or \(1\) (mod \(5\)) \(> 6\), \(n \neq 11\), a \(K_4\backslash e\) design of order \(n\) having a metamorphosis into a maximum packing of \(K_n\) with \(4\)-cycles. There exists a maximum packing of \(K_n\) with \(4\)-cycles, but it cannot be obtained from a \(K_4\backslash e\) design.

We investigate the supereulerian graph problems within planar graphs, and we prove that if a \(2\)-edge-connected planar graph \(G\) is at most three edges short of having two edge-disjoint spanning trees, then \(G\) is supereulerian except for a few classes of graphs. This is applied to show the existence of spanning Eulerian subgraphs in planar graphs with small edge cut conditions. We also determine several extremal bounds for planar graphs to be supereulerian.

Given an acyclic digraph \(D\), the phylogeny graph \(P(D)\) is defined to be the undirected graph with \(V(D)\) as its vertex set and with adjacencies as follows: two vertices \(x\) and \(y\) are adjacent if one of the arcs \((x,y)\) or \((y,x)\) is present in \(D\), or if there exists another vertex \(z\) such that the arcs \((x,z)\) and \((y,z)\) are both present in \(D\). Phylogeny graphs were introduced by Roberts and Sheng [6] from an idealized model for reconstructing phylogenetic trees in molecular biology, and are closely related to the widely studied competition graphs. The phylogeny number \(p(G)\) for an undirected graph \(G\) is the least number \(r\) such that there exists an acyclic digraph \(D\) on \(|V(G)| + r\) vertices where \(G\) is an induced subgraph of \(P(D)\). We present an elimination procedure for the phylogeny number analogous to the elimination procedure of Kim and Roberts [2] for the competition number arising in the study of competition graphs. We show that our elimination procedure computes the phylogeny number exactly for so-called “kite-free” graphs. The methods employed also provide a simpler proof of Kim and Roberts’ theorem on the exactness of their elimination procedure for the competition number on kite-free graphs.

A multiple shell \(MS\{n_1^{t_1}, n_2^{t_2}, \dots, n_r^{t_r}\}\) is a graph formed by \(t_i\) shells of widths \(n_i\), \(1 \leq i \leq r\), which have a common apex. This graph has \(\sum_{i=1}^rt_i(n_i-1) + 1\) vertices. A multiple shell is said to be balanced with width \(w\) if it is of the form \(MS\{w^t\}\) or \(MS\{w^t, (w+1)^s\}\). Deb and Limaye have conjectured that all multiple shells are harmonious, and shown that the conjecture is true for the balanced double shells and balanced triple shells. In this paper, the conjecture is proved to be true for the balanced quadruple shells.

In [BabStein], Babson and Steingrimsson introduced generalized permutation patterns that allow the requirement that two adjacent letters in a pattern must be adjacent in the permutation. In \([Kit1]\), Kitaev considered simultaneous avoidance (multi-avoidance) of two or more 3-patterns with no internal dashes, that is, where the patterns correspond to contiguous subwords in a permutation. There, either an explicit or a recursive formula was given for all but one case of simultaneous avoidance of more than two patterns. In this paper, we find the exponential generating function for the remaining case. Also, we consider permutations that avoid a pattern of the form \(x – yz\) or \(xy – z\) and begin with one of the patterns \(12\ldots k\), \(k(k-1)\ldots 1\), \(23\ldots 1k\), \((k-1)(k-2)\ldots 1k\), or end with one of the patterns \(12\ldots k\), \(k(k-1)\ldots 1\), \(1k(k-1)\ldots 2\), \(k12\ldots (k-1)\). For each of these cases, we find either the ordinary or exponential generating functions or a precise formula for the number of such permutations. Besides, we generalize some of the obtained results as well as some of the results given in \([Kit3]\): we consider permutations avoiding certain generalized \(3\)-patterns and beginning (ending) with an arbitrary pattern having either the greatest or the least letter as its rightmost (leftmost) letter.