We define an almost-convex polygon as a non-convex polygon in which any two vertices see each other inside the polygon unless they are not adjacent and belong to a chain of consecutive concave vertices. Using inclusion-exclusion techniques, we find formulas for the number of triangulations of almost-convex polygons in terms of the number and position of the concave vertices. We translate these formulas into the language of generating functions and provide several simple asymptotic estimates. We also prove that certain balanced configurations yield the maximum number of triangulations.

A coin tossing game — with a biased coin with probability \(q\) for the tail — for \(n\) persons was discussed by Moritz and Williams in \(1987\), in which the probability for players to go out in a prescribed order is described by what is commonly called the “major index” (due to Major MacMahon), which is an important statistic for the permutation group \(\mathcal{S}_n\). We first describe a variation on this game, for which the same question is answered in terms of the better known statistic “length function” in the sense of Coxeter group theory (also called “inversion number” in combinatorial literature). This entails a new bijection implying the old equality (due to MacMahon) of the generating functions for these two statistics.

Next we describe a game for \(2n\) persons where the ‘same’ question is answered in terms of the Coxeter length function for the reflection group of type \(B_n\). We conclude with some miscellaneous results and questions.

The achromatic index of a graph \(G\) is the largest integer \(k\) admitting a proper colouring of edges of \(G\) in such a way that each pair of colours appears on some pair of adjacent edges. It is shown that the achromatic index of \(K_{12}\) is \(32\).

Bollobas posed the problem of finding the least number of edges, \(f(n)\), in a maximally nonhamiltonian graph of order \(n\). Clark, Entringer and Shapiro showed \(f(n) = \left\lceil \frac{3n}{2} \right\rceil\) for all even \(n \geq 36\) and all odd \(n \geq 53\). In this paper, we give the values of \(f(n)\) for all \(n \geq 3\) and show \(f(n) = \left\lceil \frac{3n}{2} \right\rceil\) for all even \(n \geq 20\) and odd \(n \geq 17\).

Three mutually orthogonal idempotent Latin squares of order \(18\) are constructed, which can be used to obtain \(3\) HMOLS of type \(5^{18}\) and type \(23^{18}\) and to obtain a \((90, 5, 1)\)-PMD.

A graph is well-covered if every maximal independent set is also a maximum independent set. A \(1\)-well-covered graph \(G\) has the additional property that \(G – v\) is also well-covered for every point \(v\) in \(G\). Thus, the \(1\)-well-covered graphs form a subclass of the well-covered graphs. We examine triangle-free \(1\)-well-covered graphs. Other than \(C_5\) and \(K_2\), a \(1\)-well-covered graph must contain a triangle or a \(4\)-cycle. Thus, the graphs we consider have girth \(4\). Two constructions are given which yield infinite families of \(1\)-well-covered graphs with girth \(4\). These families contain graphs with arbitrarily large independence number.

A \(d\)-dimensional Perfect Factor is a collection of periodic arrays in which every \(k\)-ary \((n_1, \ldots, n_d)\) matrix appears exactly once (periodically). The one-dimensional case, with a collection of size one, is known as a De Bruijn cycle. The \(1\)- and \(2\)-dimensional versions have proven highly applicable in areas such as coding, communications, and location sensing. Here we focus on results in higher dimensions for factors with each \(n_i = 2\).

It is shown that the existence of a semi-regular automorphism group of order \(m\) of a binary design with \(v\) points implies the existence of an \(n\)-ary design with \(v/m\) points. Several examples are described. Examples of other \(n\)-ary designs are considered which place such \(n\)-ary designs in context among \(n\)-ary designs generally.

Let \(G\) be a connected graph with \(v \geq 3\). Let \(v \in V(G)\). We define \(N_k(v) = \{u|u \in V(G) \text{ and } d(u,v) = k\}\). It is proved that if for each vertex \(v \in V(G)\) and for each independent set \(S \subseteq N_2(v)\), \(|N(S) \cap N(v)| \geq |S| + 1\), then \(G\) is hamiltonian. Several previously known sufficient conditions for hamiltonian graphs follow as corollaries. It is also proved that if for each vertex \(v \in V(G)\) and for each independent set \(S \subseteq N_2(v)\), \(|N(S) \cap N(v)| \geq |S| + 2\), then \(G\) is pancyclic.

We give recursive methods for enumerating the number of orientations of a tree which can be efficiently dominated. We also examine the maximum number, \(\eta_q\), of orientations admitting an efficient dominating set in a tree with \(q\) edges. While we are unable to give either explicit formulas or recursive methods for finding \(\eta_q\), we are able to show that the growth rate of the sequence \(\langle\eta_q\rangle\) stabilizes by showing that \(\lim_{q\to\infty}\eta^\frac{1}{q}_q \) exists.

Let \(G = (V, E)\) be a finite simple graph. \(G\) is said to be a magic graph iff there exists a magic assignment of \(G\), which is a mapping \(L\) from \(E\) to \({N} = \{1, 2, \ldots\}\) such that the sums of the labels of all edges incident to the vertices in \(V\) are identical. Let \(M(G)\) be the set of all magic assignments of \(G\). For any \(L\) in \(M(G)\), define \(s(L) = \max\{L(e): e \in E\}\). Then, the magic strength of \(G\) is defined as \(m(G) = \min\{s(L): L \in M(G)\}\). In this paper, we determine the magic strengths of several classes of graphs and introduce some constructions of magic graphs. We also show that every connected graph is an induced subgraph of a magic graph.

We determine upper bounds on the number of elements in connected and \(3\)-connected matroids with fixed rank and bounded cocircuit size. The existence of these upper bounds is a Ramsey property of matroids. We also determine size type function and extremal matroids in several classes of matroids with small cocircuits.

Let \(V\) be a finite set of order \(v\). A \((v, \kappa, \lambda)\) packing design of index \(\lambda\) and block size \(u\) is a collection of \(u\)-element subsets, called blocks, such that every \(2\)-subset of \(V\) occurs in at most \(\lambda\) blocks. The packing problem is to determine the maximum number of blocks, \(\sigma(v, \kappa, \lambda)\), in a packing design. It is well known that \(\sigma(v, \kappa, \lambda) \leq [\frac{v}{\kappa}[\frac{v-1}{\kappa-1}\lambda]] = \psi(v, \kappa, \lambda)\), where \([ x ]\) is the largest integer satisfying \(x \geq [ x ]\). It is shown here that \(\sigma(v, 5, 3) = \psi(v, 5, 3)\) for all positive integers \(v \geq 5\) with the possible exceptions of \(v = 43\) and that \(\sigma(v, 5, 3) = \psi(v, 5, 3)\) for all positive integers \(v = 1, 5, 9, 17 \pmod{20}\) and \(\sigma(v, 5, 3) = \psi(v, 5, 3) – 1\) for all positive integers \(v \equiv 13 \pmod{20}\) with the possible exception of \(v = 17, 29, 33, 49\).

A graph with signed edges is orientation embedded in a surface when it is topologically embedded and a polygon preserves or reverses orientation depending on whether its sign product is positive or negative. We study orientation-embedding analogs of three facts about unsigned graph embedding: planarity is equivalent to having cographic polygon matroid, the polygon matroid of a graph determines the surfaces in which it embeds, and contraction preserves embeddability of a graph in a surface.
We treat three matroids of a signed graph. Our main results:
For a signed graph which is orientation embeddable in the projective plane, the bias and lift matroids (which coincide) are cographic.
Neither the bias nor lift nor complete lift matroid determines the surfaces in which a signed graph orientation embeds.
Of the two associated contractions of signed edges, the bias contraction does not preserve orientation embeddability but the lift contraction does.Thus the signed graphs which orientation embed in a particular surface are characterizable by forbidden lift minors.

A graph \(G\) having \(7\) vertices is called a chordal ring if its vertices can be arranged in a Hamiltonian cycle \(0, 1, 2, \ldots, n-1\) and there is a proper divisor \(d\) of \(n\) such that for all vertices \(i\) and \(j\), \(i\) is adjacent to \(j\) in \(G\) if and only if \(i+d\) is adjacent to \(j+d\) (addition modulo \(n\)). We consider here the efficacy of coloring the vertices of such a graph by the greedy algorithm applied to the vertices in the order of their appearance on the cycle. For any positive integer \(n\), let \(\Sigma_n\) denote the set of all permutations of the set \(\{1, 2, \ldots, n\}\) together with the adjacency relation \(\sim\) defined as follows: for \(\sigma\) and \(\tau\) in \(\Sigma_n\), \(\sigma \sim \tau\) if and only if there is an integer \(i\) such that \(\sigma-i = \tau-i\). (Here \(\sigma-i\) denotes the permutation of length \(n-1\) obtained by deleting \(i\) from \(\sigma\).) In this paper, we study some of the properties of the graph \((\Sigma_n, \sim)\). Two of the results obtained are the following:
(i) \((\Sigma_n, \sim)\) is a chordal ring for every positive integer \(n\);
(ii) the chromatic number of \(\Sigma_5\) is \(5\) but the greedy algorithm colors \(\Sigma_5\) in \(9\) colors.

A division of a cake \(X = X_1 \cup \cdots \cup X_n\) among \(n\) players with associated probability measures \(\mu_1, \ldots, \mu_n\) on \(X\) is said to be:

(a) exact in the ratios of \(\alpha_1 : \alpha_2 : \cdots : \alpha_n\) provided whenever \(1 \leq i, j \leq n\), \(\frac{\mu_i(X_j)} { \mu_1(X)} = \alpha_i / (\alpha_1 + \cdots + \alpha_n)\)

(b) \(\epsilon\)-near exact in the ratios \(\alpha_1 : \alpha_2 : \cdots : \alpha_n\) provided whenever \(1 \leq i, j \leq n\), \(|\frac{\mu_i(X_i)}{\mu_1(X_1)} + \cdots +\frac {\alpha_j}{\alpha_1 + \cdots + \alpha_n}| < \epsilon\)

(c) envy free in ratios \(\alpha_1 : \alpha_2 : \cdots : \alpha_n\) provided whenever \(1 \leq i, j \leq n\), \(\frac{\mu_i(X_i)}{\mu_i(X_j)} \geq \frac{\alpha_i}{\alpha_j}\).

A moving knife exact division is described for two players and it is shown there can be no finite exact algorithm for \(n \geq 2\) players. A bounded finite \(\epsilon\)-near exact algorithm is given which is used to produce a finite envy free, \(\epsilon\)-near exact algorithm.

We study bounds on the cardinality of sum-distinct sets of \(n\)-vectors with nonnegative integral components under component-wise real-number addition. A subclass of sum-distinct sets induced by an \(n \times n\) integral matrix of rank \(n\) is studied as well.

A family of subsets satisfies the Helly property when every subfamily of it, formed by pairwise intersecting subsets, has a common element. A graph is clique-Helly when the family of subsets of vertices which induces the maximal cliques of the graph satisfies the Helly property. We describe a characterization of clique-Helly graphs, leading to a polynomial time algorithm for recognizing them.

A semi-complete bigraph \(G\) has adjacency matrix
\[A = \begin{pmatrix} 0 & B \\ B^T & 0 \end{pmatrix},\]
where \(B + B^T = J – I\), so \(B\) is the adjacency matrix of a tournament \(T\) corresponding to \(G\). We determine algebraic and structural properties of this class of graphs. In particular, we obtain a condition equivalent to the connectedness of a semi-complete bigraph; moreover we determine characterizations of semi-complete bigraphs having 4 distinct eigenvalues in the case of \(G\) regular or \(A\) irreducible. In particular, a regular semi-complete bigraph has 4 distinct eigenvalues if and only if it corresponds to a doubly regular tournament.

Let \(D\) be an asymmetric digraph and \(A\) a finite group. We give a formula for the characteristic polynomial of a cyclic \(A\)-cover of \(D\). This is a generalization of a formula for the characteristic polynomial of a regular covering of a graph. Furthermore, we discuss cyclic abelian covers of \(D\).