Let $E$ be an $n$-set. The problem of packing of pairs on $E$ with a minimum number of quadruples on $E$ is settled for $n<15$ and also for $n=36t+i$, $i=3$, $6$, $9$, $12$, where $t$ is any positive integer. In the other cases of $n$ methods have been presented for constructing the packings having a minimum known number of quadruples.

A dominating set of a graph is a vertex subset that any vertex belongs to or is adjacent to. Among the many well-studied variants of domination are the so-called paired-dominating sets. A paired-dominating set is a dominating set whose induced subgraph has a perfect matching. In this paper, we continue their study. We focus on graphs that do not contain the net-graph (obtained by attaching a pendant vertex to each vertex of the triangle) or the E-graph (obtained by attaching...

The paired domination number ${\gamma }_{pr}\left(G\right)$ of a graph G is the smallest cardinality of a dominating set S of G such that ⟨S⟩ has a perfect matching. The generalized prisms πG of G are the graphs obtained by joining the vertices of two disjoint copies of G by |V(G)| independent edges. We provide characterizations of the following three classes of graphs: ${\gamma }_{pr}\left(\pi G\right)=2{\gamma }_{pr}\left(G\right)$ for all πG; ${\gamma }_{pr}\left(K₂☐G\right)=2{\gamma }_{pr}\left(G\right)$; ${\gamma }_{pr}\left(K₂☐G\right)={\gamma }_{pr}\left(G\right)$.

We are interested in dominating sets (of vertices) with the additional property that the vertices in the dominating set can be paired or matched via existing edges in the graph. This could model the situation of guards or police where each has a partner or backup. This paper will focus on those graphs in which the number of matched pairs of a minimum dominating set of this type equals the size of some maximal matching in the graph. In particular, we characterize the leafless graphs of girth seven...

Several authors have studied the graphs for which every edge is a chord of a cycle; among 2-connected graphs, one characterization is that the deletion of one vertex never creates a cut-edge. Two new results: among 3-connected graphs with minimum degree at least 4, every two adjacent edges are chords of a common cycle if and only if deleting two vertices never creates two adjacent cut-edges; among 4-connected graphs, every two edges are always chords of a common cycle.

In [3], Faudree and Gould showed that if a 2-connected graph contains no $K_{1,3}$ and P₆ as an induced subgraph, then the graph is hamiltonian. In this paper, we consider the extension of this result to cycles passing through specified vertices. We define the families of graphs which are extension of the forbidden pair $K_{1,3}$ and P₆, and prove that the forbidden families implies the existence of cycles passing through specified vertices.

It is known that Θ(log n) chords must be added to an n-cycle to produce a pancyclic graph; for vertex pancyclicity, where every vertex belongs to a cycle of every length, Θ(n) chords are required. A possibly ‘intermediate’ variation is the following: given k, 1 ≤ k ≤ n, how many chords must be added to ensure that there exist cycles of every possible length each of which passes exactly k chords? For fixed k, we establish a lower bound of ∩(n1/k) on the growth rate.

We first show that if a graph G of order n contains a hamiltonian path connecting two nonadjacent vertices u and v such that d(u)+d(v) ≥ n, then G is pancyclic. By using this result, we prove that if G is hamiltonian with order n ≥ 20 and if G has two nonadjacent vertices u and v such that d(u)+d(v) ≥ n+z, where z = 0 when n is odd and z = 1 otherwise, then G contains a cycle of length m for each 3 ≤ m ≤ max (dC(u,v)+1, [(n+19)/13]), $d_C(u,v)$ being the distance of u and v on a hamiltonian cycle of G.

The set of conjugacy classes appearing in a product of conjugacy classes in a compact, $1$-connected Lie group $K$ can be identified with a convex polytope in the Weyl alcove. In this paper we identify linear inequalities defining this polytope. Each inequality corresponds to a non-vanishing Gromov-Witten invariant for a generalized flag variety $G/P$, where $G$ is the complexification of $K$ and $P$ is a maximal parabolic subgroup. This generalizes the results for $SU\left(n\right)$ of Agnihotri and the second author and Belkale on...

We present parallel algorithms on the BSP/CGM model, with p processors, to count and generate all the maximal cliques of a circle graph with n vertices and m edges. To count the number of all the maximal cliques, without actually generating them, our algorithm requires O(log p) communication rounds with O(nm/p) local computation time. We also present an algorithm to generate the first maximal clique in O(log p) communication rounds with O(nm/p) local computation, and to generate each one of...

This work was partially supported by the Bulgarian National Science Fund under Contract No MM 1405. Part of the results were announced at the Fifth International Workshop on Optimal Codes and Related Topics (OCRT), White Lagoon, June 2007, BulgariaParallel class intersection matrices (PCIMs) have been defined and used in [6], [14], [15] for the classification of resolvable designs with several parameter sets. Resolutions which have orthogonal resolutions (RORs) have been classified in [19] for designs...