×

On partitionable, confidentially connected and unbreakable graphs. (English) Zbl 1224.05205

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
PDFBibTeX XMLCite
Full Text: EuDML