We tackle the problem of estimating the Shannon capacity of cycles of odd length. We present some strategies which allow us to find tight bounds on the Shannon capacity of cycles of various odd lengths, and suggest that the difficulty of obtaining a general result may be related to different behaviours of the capacity, depending on the “structure” of the odd integer representing the cycle length. We also describe the outcomes of some experiments, from which we derive the evidence that the Shannon capacity of odd cycles is extremely close to the value of the Lovasz theta function.

In a recent paper [1] Maynard answered a question of Harary and Manvel [2] about the reconstruction of \(square-celled \;animals\). One of his results relied on a general algebraic approach due to Alon, Caro, Krasikov, and Roditty [3]. Applying arguments of a more combinatorial nature we improve this result and give an answer to a question raised by him in [1].

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\}\).