Talmaciu, M.; Nechita, E. On partitionable, confidentially connected and unbreakable graphs. (English) Zbl 1224.05205 An. Științ. Univ. “Ovidius” Constanța, Ser. Mat. 19, No. 1, 263-274 (2011). Summary: Some problems related to security in communication networks lead to consider a new type of connectivity in graphs, namely, the confidential connectivity. In this paper, we present a characterization of unbreakable graphs using the notion of weak decomposition and give some applications of minimal unbreakable graphs. In fact, we show that a graph \(G\) is confidentially connected if and only if it does not have a star cut-set. We also show that a minimal imperfect graph does not have a star cut-set. We gave a constructive proof of the fact that every \((\alpha,\omega)\)-partitionable graph is confidentially connected for a superclass of minimal imperfect graphs. MSC: 05C17 Perfect graphs 05C85 Graph algorithms (graph-theoretic aspects) 05C90 Applications of graph theory 05C50 Graphs and linear algebra (matrices, eigenvalues, etc.) 05C12 Distance in graphs Keywords:unbreakable graphs; confidentially connected; star cut set; weakly decomposition; recognition algorithm PDFBibTeX XMLCite \textit{M. Talmaciu} and \textit{E. Nechita}, An. Științ. Univ. ``Ovidius'' Constanța, Ser. Mat. 19, No. 1, 263--274 (2011; Zbl 1224.05205) Full Text: EuDML