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.