Restricted Edge-Connectivity and Minimum Edge-Degree

Abstract

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.