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.

In a paper of Harary and Plantholt, they concluded by noting that they knew of no generalization of the leaf edge exchange (\(LEE\)) transition sequence result on spanning trees to other natural families of spanning subgraphs. Now, we give two approaches for such a generalization. We define two kinds of \(LEE\)-graphs over the set of all connected spanning \(k\)-edge subgraphs of a connected graph \(G\), and show that both of them are connected for a \(2\)-connected graph \(G\).

We look at binary strings of length \(n\) which contain no odd run of zeros and express the total number of such strings, the number of zeros, the number of ones, the total number of runs, and the number of levels, rises, and drops as functions of the Fibonacci and Lucas numbers and also give their generating functions. Furthermore, we look at the decimal value of the sum of all binary strings of length \(n\) without odd runs of zeros considered as base \(2\) representations of decimal numbers, which interestingly enough are congruent (mod \(3\)) to either \(0\) or a particular Fibonacci number. We investigate the same questions for palindromic binary strings with no odd runs of zeros and obtain similar results, which generally have different forms for odd and even values of \(n\).

In this paper, we characterize the potentially \(K_4\)-graphic sequences. This characterization implies the value \(\sigma(K_4,n)\), which was conjectured by P. Erdős, M. S. Jacobson, and J. Lehel [1] and was confirmed by R. J. Gould, M. S. Jacobson, and J. Lehel [2] and Jiong-Sheng Li and Zixia Song [5], independently.

The graph …….is called a kite and the decomposition of \(K_n\) into kites is called a kite system. Such systems exist precisely when \(n = 0\) or \(1\) (mod \(8\)). In \(1975\), C. C. Lindner and A. Rosa solved the intersection problem for Steiner triple systems. The object of this paper is to give a complete solution to the triangle intersection problem for kite systems (\(=\) how many triangles can two kite systems of order \(n\) have in common). We show that if \(x \in \{0, 1, 2, \dots, n(n-1)/8\}\), then there exists a pair of kite systems of order \(n\) having exactly \(n\) triangles in common.

A directed balanced incomplete block design (\(DB\)(\(k\), \(\lambda\);\(v\))) \((X, \mathcal{B})\) is called self-converse if there is an isomorphic mapping \(f\) from \((X, \mathcal{B})\) to \((X, \mathcal{B}^{-1})\), where \(\mathcal{B}^{-1} = \{B^{-1} : B \in \mathcal{B}\}\) and \(B^{-1} = (x_k,x_{k-1},\ldots,x_2,x_1)\) for \(B=(x_1,x_2,\ldots,x_{k-1},x_{k})\). In this paper, we give the existence spectrum for self-converse \(DB\)(\(4\),\(\lambda\);\(v\)) for any \(\lambda \geq 1\).

A sequence \(\pi = (d_1, \dots, d_n)\) of nonnegative integers is graphic if there exists a graph \(G\) with \(n\) vertices for which \(d_1, \dots, d_n\) are the degrees of its vertices. \(G\) is referred to as a realization of \(\pi\). Let \(P\) be a graph property. A graphic sequence \(\pi\) is potentially \(P\)-graphic if there exists a realization of \(\pi\) with the graph property \(P\). Similarly, \(\pi\) is forcibly \(P\)-graphic if all realizations of \(\pi\) have the property \(P\). We characterize potentially Halin graph-graphic sequences, forcibly Halin graph-graphic sequences, and forcibly cograph-graphic sequences.

We establish the nonexistence of:(i) Steiner \(t\)-\((v,k)\) trades of volume \(s\), for \(2^t + 2^{t-1} < s t+1\) and volume \(s < (t-1)2^t + 2\).

Using R. C. Read’s superposition method, we establish a formula for the enumeration of Euler multigraphs, with loops allowed and with given numbers of edges. In addition, applying Burnside’s Lemma and our adaptation of Read’s superposition method, we also derive a formula for the enumeration of Euler multigraphs without loops — via the calculation of the number of perfect matchings of the complement of complete multipartite graphs. MAPLE is employed to implement these enumerations. For one up to \(13\) edges, the numbers of nonisomorphic Euler multigraphs with loops allowed are:\(1, 3, 6, 16, 34, 90, 213, 572, 1499, 4231, 12115, 36660, 114105\) respectively, and for one up to \(16\) edges, the numbers of nonisomorphic Euler multigraphs without loops are:\(0, 1, 1, 4, 4, 15, 22, 68, 131, 376, 892, 2627, 7217, 22349, 69271, 229553\) respectively. Simplification of these methods yields the numbers of multigraphs with given numbers of edges, results which also appear to be new. Our methods also apply to multigraphs with essentially arbitrary constraints on vertex degrees.

In this paper, we determine the number of all maximal \(k\)-independent sets in the generalized lexicographical product of graphs. We construct a polynomial that calculates this number using the concept of Fibonacci polynomials and generalized Fibonacci polynomials. Also, for special graphs, we give the recurrence formula.

For a \(3\)-vertex coloring, a face of a triangulation whose vertices receive all three colors is called a vivid face with respect to it. In this paper, we show that for any triangulation \(G\) with \(n\) faces, there exists a coloring of \(G\) with at least \( \frac{1}{2}n\) faces and construct an infinite series of plane triangulations such that any \(3\)-coloring admits at most \(\frac{1}{5}(3n- 2)\) vivid faces.

A projective plane is equivalent to a disk with antipodal points identified. A graph is projective planar if it can be drawn on the projective plane with no crossing edges. A linear time algorithm for projective planar embedding has been described by Mohar. We provide a new approach that takes \(O(n^2)\) time but is much easier to implement. We programmed a variant of this algorithm and used it to computationally verify the known list of all the projective plane obstructions.

One application for this work is graph visualization. Projective plane embeddings can be represented on the plane and can provide aesthetically pleasing pictures of some non-planar graphs. More important is that it is highly likely that many problems that are computationally intractable (for example, NP-complete or #P-complete) have polynomial time algorithms when restricted to graphs of fixed orientable or non-orientable genus. Embedding the graph on the surface is likely to be the first step for these algorithms.

We consider the nonexistence of \(e\)-perfect codes in the Johnson scheme \(J(n, w)\). It is proved that for each \(J(2w + 3p, w)\) for \(p\) prime and \(p \neq 2, 5\), \(J(2w + 5p, w)\) for \(p\) prime and \(p \neq 3\), and \(J(2w + p^2, w)\) for \(p\) prime, it does not contain non-trivial \(e\)-perfect codes.

A graph \(G\) is called \(f\)-factor-covered if every edge of \(G\) is contained in some \(f\)-factor. \(G\) is called \(f\)-factor-deleted if \(G\) – \(e\) contains an \(f\)-factor for every edge \(e\). Babler proved that every \(r\)-regular, \((r – 1)\)-edge-connected graph of even order has a \(1\)-factor. In the present article, we prove that every \(2r\)-regular graph of odd order is both \(2m\)-factor-covered and \(2m\)-factor-deleted for all integers \(m\), \(1 \leq m \leq r – 1\), and every \(r\)-regular, \((r – 1)\)-edge-connected graph of even order is both \(m\)-factor-covered and \(m\)-factor-deleted for all integers \(m\), \(1 \leq m \leq \left\lfloor \frac{r}{2} \right\rfloor\).

The convex hull of a subset \(A\) of \(V(G)\), where \(G\) is a connected graph, is defined as the smallest convex set in \(G\) containing \(A\). The hull number of \(G\) is the cardinality of a smallest set \(A\) whose convex hull is \(V(G)\). In this paper, we give the hull number of the composition of two connected graphs.

The basis number \(b(G)\) of a graph \(G\) is defined to be the least integer \(d\) such that \(G\) has a \(d\)-fold basis for its cycle space. In this paper, we investigate the basis number of the direct product of theta graphs and paths.

Large sets of balanced incomplete block (\(BIB\)) designs and resolvable \(BIB\) designs are discussed. Some recursive constructions of such large sets are given. Some existence results, in particular for practical \(k\), are reviewed.

We consider point-line geometries having three points on every line, having three lines through every point (\(bi\)-\(slim\; geometries\)), and containing triangles. We give some (new) constructions and we prove that every flag-transitive such geometry either belongs to a certain infinite class described by Coxeter a long time ago, or is one of three well-defined sporadic ones, namely, The Möbius-Kantor geometry on \(8\) points, The Desargues geometry on \(10\) points,A unique infinite example related to the tiling of the real Euclidean plane in regular hexagons.We also classify the possible groups.

Let \(G\) be a simple graph such that \(\delta(G) \geq \lfloor\frac{|V(G)|}{2}\rfloor + k\), where \(k\) is a non-negative integer, and let \(f: V(G) \to \mathbb{Z}^+\) be a function having the following properties (i)\(\frac{d_G(x)}{2}-\frac{k+1}{2}\leq f(x)\leq \frac{d_G(x)}{2}+\frac{k+1}{2}\) for every \(x \in V(G)\), (ii)\(\sum\limits_{x\in V(G)}f(x)=|E(G)|\). Then \(G\) has an orientation \(D\) such that \(d^+_D(x) = f(x)\), for every \(x \in V(G)\).

The so-called multi-restricted numbers generalize and extend the role of Stirling numbers and Bessel numbers in various problems of combinatorial enumeration. Multi-restricted numbers of the second kind count set partitions with a given number of parts, none of whose cardinalities may exceed a fixed threshold or “restriction”. The numbers are shown to satisfy a three-term recurrence relation. Both analytic and combinatorial proofs for this relation are presented. Multi-restricted numbers of both the first and second kinds provide connections between the orbit decompositions of subsets of powers of a finite group permutation representation, in which the number of occurrences of elements is restricted. An exponential generating function for the number of orbits on such restricted powers is given in terms of powers of partial sums of the exponential function.

A class of graphs called generalized ladder graphs is defined. A sufficient condition for pairs of these graphs to be chromatically equivalent is proven. In addition, a formula for the chromatic polynomial of a graph of this type is proven. Finally, the chromatic polynomials of special cases of these graphs are explicitly computed.

Let \(k \geq 3\) be odd and \(G = (V(G), E(G))\) be a \(k\)-edge-connected graph. For \(X \subseteq V(G)\), \(e(X)\) denotes the number of edges between \(X\) and \(V(G) – X\). We here prove that if \(\{s_i, t_i\} \subseteq X_i \subseteq V(G)\), \(i = 1, 2\), \(X_1 \cap X_2 = \emptyset\), \(e(X_1) \leq 2k-2\) and \(e(X_2) < 2k-1\), then there exist paths \(P_1\) and \(P_2\) such that \(P_i\) joins \(s_i\) and \(t_i\), \(V(P_i) \subseteq X_i\) (\(i = 1, 2\)) and \(G – E(P_1 \cup P_2)\) is \((k-2)\)-edge-connected. And in fact, we give a generalization of this result and some other results about paths not containing given edges.

Optimal binary linear codes of length \(18\) containing the \([6, 5, 2]\otimes[ 3, 1, 3]\) product code are presented. It is shown that these are \([18, 9, 5]\) and \([18, 8, 6]\) codes. The soft-decision maximum-likelihood decoding complexity of these codes is determined. From this point of view, these codes are better than the \([18, 9, 6]\) code.