Recently, in connection with the classification problem for non-Cayley tetravalent metacirculant graphs, three families of special tetravalent metacirculant graphs, denoted by \(\Phi_1, \Phi_2\), and \(\Phi_3\), have been defined [11]. It has also been shown [11] that any non-Cayley tetravalent metacirculant graph is isomorphic to a union of disjoint copies of a graph in one of the families \(\Phi_1, \Phi_2\), or \(\Phi_3\). A natural question raised from the result is whether all graphs in these families are non-Cayley. In this paper we determine the automorphism groups of all graphs in the family \(\Phi_2\). As a corollary, we show that every graph in \(\Phi_2\) is a connected non-Cayley tetravalent metacirculant graph.

Let \(G\) be a connected graph and \(S \subset E(G)\). If \(G – S\) is disconnected without isolated vertices, then \(S\) is called a restricted edge-cut of \(G\). The restricted edge-connectivity \(\lambda’ = \lambda'(G)\) of \(G\) is the minimum cardinality over all restricted edge-cuts of \(G\). A connected graph \(G\) is called \(\lambda’\)-connected, if \(\lambda'(G)\) exists. For a \(\lambda’\)-connected graph \(G\), Esfahanian and Hakimi have shown, in 1988, that \(\lambda'(G) \leq \xi(G)\), where \(\xi(G)\) is the minimum edge-degree. A \(\lambda’\)-connected graph \(G\) is called \(\lambda’\)-optimal, if \(\lambda'(G) = \xi(G)\).

Let \(G_1\) and \(G_2\) be two disjoint \(\lambda’\)-optimal graphs. In this paper we investigate the cartesian product \(G_1 \times G_2\) to be \(\lambda’\)-optimal. In addition, we discuss the same question for another operation on \(G_1\) and \(G_2\), and we generalize a recent theorem of J.-M. Xu on non \(\lambda’\)-optimal graphs.

The niche graph of a digraph \(D\) is the undirected graph defined on the same vertex set in which two vertices are adjacent if they share either a common in-neighbor or a common out-neighbor in \(D\). A hierarchy of graphs exists, depending on the condition of being the niche graph of a digraph having, respectively, no cycles, no cycles of length two, no loops, or loops. Our goal is to classify in this hierarchy all graphs of order \(n \geq 3\) having a generated subgraph isomorphic to the discrete graph on \(n – 2\) vertices.

We enumerate the bases of the bicircular matroid on \(K_{m,n}\). The structure of bases of the bicircular matroid in relation to the bases of the cycle matroid is explored. The techniques herein may enable the enumeration of the bases of bicircular matroids on larger classes of graphs; indeed one of the motivations for this work is to show the extendibility of the techniques recently used to enumerate the bases of the bicircular matroid on \(K_n\).

Motivated by the work of Granville, Moisiadis and Rees, we consider in this paper complementary \(P_3\)-packings of \(K_v\). We prove that a maximum complementary \(P_3\)-packing of \(K_v\) (with \(\lfloor\frac{v}{4} \lfloor \frac{2(v-1)}{3}\rfloor \rfloor P_3s\)) exists for all integers \(v \geq 4\), except for \(v = 9\) and possibly for \(v \in \{24, 27, 30, 33, 36, 39, 42, 57\}\).

It is proved that there is no maximal partial spread of size \(115\) in \(\mathrm{PG}(3,11)\).

In this short note, using the method developed in [10] and [11], we construct a highly symmetrical, non-simple, attractive \(7\)-Venn diagram. This diagram has the minimum number of vertices, \(21\). The only similar two, published in [1] and [11], differ from ours in many ways. One of them was found by computer search [1]. Both of them are “necklace” type Venn diagrams (see [14] for definition), but ours is not.

A graph is a unit interval graph (respectively, an \(\tilde{n}\)-graph) if we can assign to each vertex an open interval of unit length (respectively, a set of \(n\) consecutive integers) so that edges correspond to pairs of intervals (respectively, of sets) that overlap. Sakai [14] and Troxell [18] provide a linear time algorithm to find the smallest integer \(n\) so that a unit interval graph is an \(\mathbb{A}\)-graph, for the particular case of reduced connected graphs with chromatic number \(3\). This work shows how to obtain such smallest \(n\) for arbitrary graphs, by establishing a relationship with the work by Bogart and Stellpflug [1] in the theory of semiorders.

For words of length \(n\), generated by independent geometric random variables, we consider the probability that these words avoid a given consecutive \(3\)-letter pattern. As a consequence, we count permutations in \(S_n\) avoiding consecutive \(3\)-letter patterns.

A mimeomatroid is a matroid union of a matroid with itself. We develop several properties of mimeomatroids, including a generalization of Rado’s theorem, and prove a weakened version of a matroid conjecture by Rota [2].