A graph \(G\) is maximally non-hamiltonian \((MNH)\) if \(G\) is not hamiltonian but becomes hamiltonian after adding an arbitrary new edge. Bondy \([2]\) showed that the smallest size \((=\)number of edges) in a \(MNH\) graph of order \(n\) is at least \(\left\lceil\frac{3n}{2}\right\rceil\) for \(n \geq 7\). The fact that equality may hold for infinitely many \(n\) was suggested by Bollobas [1]. This was confirmed by Clark, Entringer, and Shapiro (see [5,6]) and by Xiaobui, Wenzhou, Chengxue, and Yuanscheng [8] who set the values of the size of smallest \(MNH\) graphs for all small remaining orders \(n\). An interesting question of Clark and Entringer [8] is whether for infinitely many \(n\) the smallest \(MNH\) graph of order \(n\) is not unique. A positive answer – the existence of two non-isomorphic smallest \(MNH\) graphs for infinitely many \(n\) follows from results in \([5], [4], [6]\), and \([8]\). But, there still exist infinitely many orders \(n\) for which only one smallest \(MNH\) graph of order \(n\) is known.

We prove that for all \(n \geq 88\) there are at least \(\tau(n) > 3\) smallest \(MNH\) graphs of order \(n\), where \(\lim_{n\to\infty} \tau(n) = \infty\). Thus, there are only finitely many orders \(n\) for which the smallest \(MNH\) graph is unique.

We deal with \((a, d)\)-antimagic labelings of the prisms.
A connected graph \(G = (V, E)\) is said to be \((a, d)\)-antimagic if there exist positive integers \(a, d\) and a bijection \(f: E \to \{1, 2, \ldots, |E|\}\) such that the induced mapping \(g_f: V \to {N}\), defined by \(g_f(v) = \sum \{f(u, v): (u, v) \in E(G)\}\), is injective and \(g_f(V) = \{a, a + d, \ldots, a + (|V| – 1)d\}\).

We characterize \((a, d)\)-antimagic prisms with even cycles and we conjecture that prisms with odd cycles of length \(n\), \(n \geq 7\), are \((\frac{n+7}{2}, 4)\)-antimagic.

We establish some basic facts about sign-patterns of orthogonal matrices, and use these facts to characterize the sign-nonsingular matrices which are sign-patterns of orthogonal matrices.

In this paper, we give some properties of balanced labeling, prove that the graph \((m^2 + 1)C_4\) is balanced, and also solve the balanceness of snakes \(C_m(n)\).

In this note, we verify two conjectures of Catlin in [J.Graph Theory \(13 (1989)465-483\)] for graphs with at most \(11\) vertices. These are used to prove the following theorem, which improves prior results in \([10]\) and \([13]\):

Let \(G\) be a 3-edge-connected simple graph with order \(n\). If \(n\) is large and if for every edge \(uv \in E(G)\), \(d(u) + d(v) \geq \frac{n}{6} – 2\), then either \(G\) has a spanning eulerian subgraph or $G$ can be contracted to the Petersen graph.

Let \(G\) be a graph. A vertex subversion strategy of \(G\), \(S\), is a set of vertices in \(G\) whose closed neighborhood is deleted from \(G\). The survival-subgraph is denoted by \(G/S\). The vertex-neighbor-integrity of \(G\), \(VNI(G)\), is defined as:

\(VNI(G) = \min_{|S|} {|S| + w(G/S)}\)

where \(S\) is any vertex subversion strategy of \(G\), and \(w(G/S)\) is the maximum order of the components of \(G/S\). In this paper, we evaluate the vertex-neighbor-integrity of the powers of cycles, and show that among the powers of the \(n\)-cycle, the maximum vertex-neighbor-integrity is \(\left\lceil{2}\sqrt{n}\right\rceil – 3\) and the minimum vertex-neighbor-integrity is \(\left\lceil\frac{n}{2\left\lfloor\frac{n}{2}\right\rfloor} + 1\right\rceil\).

What is the 2-packing number of the \(1 \times m \times n\) complete grid graph? Fisher solved this for \(1 \times m \times n\) grids for all \(m\) and \(n\). We answer this for \(2 \times m \times n\) grids for all \(m\) and \(n\), and for \(3 \times 3 \times n\), \(3 \times 4 \times n\), \(3 \times 7 \times n\), \(4 \times 4 \times n\), and \(5 \times 5 \times n\) grids for all \(n\). Partial results are given for other sizes.

A Pandiagonal magic square (PMS) of order \(n\) is a square matrix which is an arrangement of integers \(0, 1, \ldots, n^2-1\) such that the sums of each row, each column, and each extended diagonal are the same. In this paper, we use the Step method to construct a PMS of order \(n\) for each \(n > 3\) and \(n\) is not singly-even. We discuss how to enumerate the number of PMSs of order \(n\) constructed by the Step method, and we get the number of nonequivalent PMSs of order \(8\) with the top left cell \(0\) is \(4,176,000\) and the number of nonequivalent PMSs of order \(9\) with the top left cell \(0\) is \(1,492,992\).

In this paper, we consider total clique covers and uniform intersection numbers on multifamilies. We determine the uniform intersection numbers of graphs in terms of total clique covers. From this result and some properties of intersection graphs on multifamilies, we determine the uniform intersection numbers of some families of graphs. We also deal with the \(NP\)-completeness of uniform intersection numbers.

An oriented triple system of order \(v\), denoted OTS\((v)\), is said to be \(d\)-cyclic if it admits an automorphism consisting of a single cycle of length \(d\) and \(v-d\) fixed points, \(d\geq 2\). In this paper, we give necessary and sufficient conditions for the existence of \(d\)-cyclic OTS\((v)\). We solve the analogous problem for directed triple systems.

Let \(A_m(n, k)\) denote the number of permutations of \(\{1, \ldots, n\}\) with exactly \(k\) rises of size at least \(m\). We show that, for each positive integer \(m\), the \(A_m(n, k)\) are asymptotically normal.

Let \(G\) be a graph of order \(n\) and \( X\) a given vertex subset of \(G\). Define the parameters:
\(\alpha(V) = \max\{|S| \mid S \text{ is an independent set of vertices of the subgraph } G(X) \text{ in } G \text{ induced by } X\}\)
and
\(\sigma_k(X) = \min\{|\Sigma_{i=1}^{k}d(x_i)| \mid \{x_1,x_2,\ldots,x_k\} \text{ is an independent vertex set in } G[X]\}\)
A cycle \(C\) of \(G\) is called \(X\)-longest if no cycle of \(G\) contains more vertices of \(X\) than \(C\). A cycle \(C’\) of \(G\) is called \(X\)-dominating if all neighbors of each vertex of \(X\setminus V(C)\) are on \(C\). In particular, \(G\) is \(X\)-eyclable if \(G\) has an \(X\)-cycle, i.e., a cycle containing all vertices of \(X\). Our main result is as follows:
If \(G\) is \(1\)-tough and \(\sigma_3(X) \geq n\), then \(G\) has an \(X\)-longest cycle \(C\) such that \(C\) is an \(X\)-dominating cycle and \(|V(C) \cap X| \geq \min\{|X|. |X| + \frac{1}{3}\sigma_3(X) – \sigma(X)\}\), which extends the well-known results of D. Bauer et al. [2] in terms of \(X\)-cyclability. Finally, if \(G\) is \(2\)-tough and \(\sigma_3(X) \geq n\), then \(G\) is \(X\)-cyelable.

In 1992, Mahmoodian and Soltankhah conjectured that, for all \(0 \leq i \leq t\), a \((v, k, t)\) trade of volume \(2^{t+1} – 2^{t-i}\) exists. In this paper we prove this conjecture and, as a corollary, show that if \(s \geq (2t – 1)2^t\) then there exists a \((v, k, t)\) trade of volume \(s\).

We prove two new characterization theorems for finite Moufang polygons, one purely combinatorial, another group-theoretical. Both follow from a result of Andries Brouwer on the connectedness of the geometry opposite a flag in a finite generalized polygon.

Cyclonomial coefficients are defined as a generalization of binomial coefficients. It is proved that each natural number can be expressed, in a unique way, as the sum of cyclonomial coefficients, satisfying certain conditions. This cyclonomial number system generalizes the well-known binomial number system. It appears that this system is the appropriate number system to index the words of the lexicographically ordered code \(L^q(n, k)\). This code consists of all words of length \(n\) over an alphabet of \(q\) symbols, such that the sum of the digits is constant. It provides efficient algorithms for the conversion of such a codeword to its index, and vice versa.

We investigate the connections between families of graphs closed under (induced) subgraphs and their forbidden (induced) subgraph characterizations. In particular, we discuss going from a forbidden subgraph characterization of a family \(\mathbb{P}\) to a forbidden induced subgraph characterization of the family of line graphs of members of \(\mathbb{P}\) in the most general case. The inverse problem is considered too.

A family of double circulant quasi-cyclic codes is constructed from the incidence matrices of difference sets associated with hyperplanes in projective space. A subset of these codes leads to a class of doubly-even self-orthogonal codes, and two classes of self-dual codes.

All nonisomorphic \(2\)-\((21, 6, 3)\) designs with automorphisms of order \(7\) or \(5\) were found, and the orders of their groups of automorphisms were determined. There are \(33\) nonisomorphic \(2\)-\((21, 6, 3)\) designs with automorphisms of order \(7\) and \(203\) with automorphisms of order \(5\).

Let \(G\) be a graph with even order \(p\) and let \(k\) be a positive integer with \(p \geq 2k + 2\). It is proved that if the toughness of \(G\) is at least \(k\), then the subgraph of \(G\) obtained by deleting any \(2k – 1\) edges or \(k\) vertices has a perfect matching. Furthermore, we show that the results in this paper are best possible.

The following problem, known as the Strong Coloring Problem for the group \(G\) (SCP\(_G\)) is investigated for various permutation groups \(G\). Let \(G\) be a subgroup of \(S_h\), the symmetric group on \(\{0, \ldots, h-1\}\). An instance of SCP\(_G\) is an \(h\)-ary areflexive relation \(\rho\) whose group of symmetry is \(G\) and the question is “does \(\rho\) have a strong \(h\)-coloring”? Let \(m \geq 3\) and \(D_m\) be the Dihedral group of order \(m\). We show that SCP\(_{D_m}\) is polynomial for \(m = 4\), and NP-complete otherwise. We also show that the Strong Coloring Problem for the wreath product of \(H\) and \(K\) is in \( {P}\) whenever both SCP\(_H\) and SCP\(_K\) are in \( {P}\). This, together with the algorithm for \(D_4\) yields an infinite new class of polynomially solvable cases of SCP\(_G\).

We deal with the concept of packings in graphs, which may be regarded as a generalization of the theory of graph design. In particular, we construct a vertex- and edge-disjoint packing of \(K_n\) (where \(\frac{n}{2} \mod 4\) equals 0 or 1) with edges of different cyclic length. Moreover, we consider edge-disjoint packings in complete graphs with uniform linear forests (and the resulting packings have special additional properties). Further, we give a relationship between finite geometries and certain packings which suggests interesting questions.

A homomorphism from a graph to another graph is an edge preserving vertex mapping. A homomorphism naturally induces an edge mapping of the two graphs. If, for each edge in the image graph, its preimages have \(k\) elements, then we have an edge \(k\)-to-\(1\) homomorphism. We characterize the connected graphs which admit edge \(2\)-to-\(1\) homomorphism to a path, or to a cycle. A special case of edge \(k\)-to-\(1\) homomorphism — \(k\)-wrapped quasicovering — is also considered.

Let \(G\) be a \(2\)-connected simple graph with order \(n\) (\(n \geq 5\)) and minimum degree 6. This paper proves that if \(|N(u) \cup N(v)| \geq n – \delta + 2\) for any two nonadjacent vertices \(u, v \in V(G)\), then \(G\) is edge-pancyclic, with a few exceptions. Under the same condition, we prove that if \(u, v \in V(G)\) and \(\{u, v\}\) is not a cut set and \(N(u) \cap N(v) \neq \phi\) when \(uv \in E(G)\), then there exist \(u\)–\(v\) paths of length from \(d(u, v)\) to \(n – 1\).

The purpose of this paper is to extend the well-known concepts of additive permutations and bases of additive permutations to the case when repeated elements are permitted; that means that the basis (an ordered set) can become an ordered multiset. Certain special cases are studied in detail and all bases with repeated elements up to cardinality six are enumerated, together with their additive permutations.

We show how lattice paths and the reflection principle can be used to give easy proofs of unimodality results. In particular, we give a “one-line” combinatorial proof of the unimodality of the binomial coefficients. Other examples include products of binomial coefficients, polynomials related to the Legendre polynomials, and a result connected to a conjecture of Simion.

The search for homometric structures, i.e., non-congruent structures sharing the same autocorrelation function, is shown to be of a combinatorial nature and can be studied using purely algebraic techniques. Several results on the existence of certain homometric structures which contradict a theorem by S. Piccard are proved based on a polynomial representation model and the factorization of polynomials over the rationals. Combinatorial arguments show that certain factorizations do not lead to counterexamples to S. Piccard’s theorem.

Let \(G = (V, E)\) be a graph. For any real valued function \(f: V \to \mathbb{R}\) and \(S \subseteq V\), let \(f(S) = \sum_{u \in S} f(u)\). Let \(c, d\) be positive integers such that \(\gcd(c, d) = 1\) and \(0 < \frac{c}{d} \leq 1\). A \(\frac{c}{d}\)-dominating function \(f\) is a function \(f: V \to \{-1, 1\}\) such that \(f[v] \geq 1\) for at least \(\frac{c}{d}\) of the vertices \(v \in V\). The \(\frac{c}{d}\)-domination number of \(G\), denoted by \(\gamma_{\frac{c}{d}}(G)\), is defined as \(\min\{f(V) | f\) is a \(\frac{c}{d}\)-dominating function on \(G\}\). We determine a sharp lower bound on \(\gamma_{\frac{c}{d}}(G)\) for regular graphs \(G\), determine the value of \(\gamma_{\frac{c}{d}}(G)\) for an arbitrary cycle \(C_n\), and show that the decision problem PARTIAL SIGNED DOMINATING FUNCTION is \(NP\)-complete.

The vertex set of a halved cube \(Q’_d\) consists of a bipartition vertex set of a cube \(Q_d\) and two vertices are adjacent if they have a common neighbour in the cube. Let \(d \geq 5\). Then it is proved that \(Q’_d\) is the only connected, \(\binom{d}{3}\)-regular graph on \(2^d\) vertices in which every edge lies in two \(d\)-cliques and two \(d\)-cliques do not intersect in a vertex.

Geometrical representations of certain classical number tables modulo a given prime power (binomials, Gaussian \(g\)-binomials and Stirling numbers of \(1st\) and \(2nd\) kind) generate patterns with self-similarity features. Moreover, these patterns appear to be strongly related for all number tables under consideration, when a prime power is fixed.

These experimental observations are made precise by interpreting the recursively defined number tables as the output of certain cellular automata \((CA)\). For a broad class of \(CA\) it has been proven \([11]\) that the long time evolution can generate fractal sets, whose properties can be understood by means of hierarchical iterated function systems. We use these results to show that the mentioned number tables (mod \(p^v\)) induce fractal sets which are homeomorphic to a universal fractal set denoted by \(\mathcal{S}_{p^v}\) which we call Sierpinski triangle (mod \(p^v\)).