We address the problem of determining all sets which form minimal covers of maximal cliques for interval graphs. We produce an algorithm enumerating all minimal covers using the C-minimal elements of the interval order, as well as an independence Metropolis sampler. We characterize maximal removable sets, which are the complements of minimal covers, and produce a distinct algorithm to enumerate them. We use this last characterization to provide bounds on the maximum number of minimal covers for an interval order with a given number of maximal cliques, and present some simulation results on the number of minimal covers in different settings.

A directed triple system of order \(v\), denoted by DTS\((v)\), is a pair \((X,\mathcal{B})\) where \(X\) is a \(v\)-set and \(\mathcal{B}\) is a collection of transitive triples on \(X\) such that every ordered pair of \(X\) belongs to exactly one triple of \(\mathcal{B}\). A DTS\((v)\) is called pure and denoted by PDTS\((v)\) if \((x,y,z) \in \mathcal{B}\) implies \((z,y,x) \notin \mathcal{B}\). A large set of disjoint PDTS\((v)\) is denoted by LPDTS\((v)\). In this paper, we establish the existence of LPDTS\((v)\) for \(v \equiv 0,4 \pmod{6}\), \(v\geq 4\).

We extend and give short proofs of some recent results regarding some classes of rational difference equations.

The skewness \(sk(G)\) of a graph \(G = (V, E)\) is the smallest integer \(sk(G) \geq 0\) such that a planar graph can be obtained from \(G\) by the removal of \(sk(G)\) edges. The splitting number \(sp(G)\) of \(G\) is the smallest integer \(sp(G) \geq 0\) such that a planar graph can be obtained from \(G\) by \(sp(G)\) vertex splitting operations. The vertex deletion \(vd(G)\) of \(G\) is the smallest integer \(vd(G) \geq 0\) such that a planar graph can be obtained from \(G\) by the removal of \(vd(G)\) vertices. Regular toroidal meshes are popular topologies for the connection networks of SIMD parallel machines. The best known of these meshes is the rectangular toroidal mesh \(C_m \times C_n\), for which is known the skewness, the splitting number and the vertex deletion. In this work we consider two related families: a triangulation \(T_{m,n}\) of \(C_m \times C_n\) in the torus, and an hexagonal mesh \(H_{m,n}\), the dual of \(\mathcal{T}_{C_m\times C_n}\) in the torus. It is established that \(sp(T_{m,n}) = vd(T_{m,n}) = sk(H_{C_m\times C_n}) = sp(\mathcal{H}_{C_m\times C_n}) = vd(\mathcal{H}_{m,n}) = \min\{m,n\}\) and that \(sk(\mathcal{T}_{C_m\times C_n}) = 2\min\{m, n\}\).

Exploiting the empirical observation that the probability of \(k\) fixed points in a Welch-Costas permutation is approximately the same as in a random permutation of the same order, we propose a stochastic model for the most probable maximal number of fixed points in a Welch-Costas permutation.

Let \(\gamma_c(G)\)be the connected domination number of \(G\) and \(\gamma_t(G)\) be the tree domination number of \(G\). In this paper, we study the connected domination number and tree domination of \(P(n,k)\), and show that \(\gamma_{tr}(P(n, 4)) = \gamma_c(P(n, 4)) = n-1\) for \(n \geq 17\), \(\gamma_{tr}(P(n, 6)) = \gamma_c(P(n, 6)) = n-1\) for \(n \geq 25\), and \(\gamma_{tr}(P(n,8)) = \gamma_c(P(n,8)) = n-1\) for \(n \geq 33\).

A cut \((A, B)\) (where \(B = V – A\)) in a graph \(G = (V, E)\) is called internal if and only if there exists a vertex \(x \in A\) that is not adjacent to any vertex in \(B\) and there exists a vertex \(y \in B\) such that it is not adjacent to any vertex in \(A\). In this paper, we present a theorem regarding the arrangement of cliques in a chordal graph with respect to its internal cuts. Our main result is that given any internal cut \((A, B)\) in a chordal graph \(G\), there exists a clique with \(\kappa(G) + 1\) vertices (where \(\kappa(G)\) is the vertex connectivity of \(G\)) such that it is (approximately) bisected by the cut \((A, B)\). In fact, we give a stronger result: For any internal cut \((A, B)\) of a chordal graph, and for each \(i\), \(0 \leq i \leq \kappa(G) + 1\), there exists a clique \(K_i\) such that \(|A \cap K_i| = \kappa(G) + 1\), \(|A \cap K_i| = i\), and \(|B \cap K_i| = \kappa(G) + 1- i\).

An immediate corollary of the above result is that the number of edges in any internal cut (of a chordal graph) should be \(\Omega(k^2)\) where \(\kappa(G)\). Prompted by this observation, we investigate the size of internal cuts in terms of the vertex connectivity of the chordal graphs. As a corollary, we show that in chordal graphs, if the edge connectivity is strictly less than the minimum degree, then the size of the mincut is at least \(\frac{\kappa(G)(\kappa(G) + 1)}{2}\), where \(\kappa(G)\) denotes the vertex connectivity. In contrast, in a general graph the size of the mincut can be equal to \(\kappa(G)\). This result is tight.

We determine the automorphism group and the spectrum of the folded hypercube. In addition, we define the Bi-folded hypercube and determine its spectrum.