Operator decomposition of graphs

Abstract EN

In this paper we introduce a new form of decomposition of graphs, the (P, Q)-decomposition.

We first give an optimal algorithm for finding the 1-decomposition of a graph which is a special case of the (P, Q)-decomposition which was first introduced in [21].

We then examine the connections between the 1-decomposition and well known forms of decomposition of graphs, namely, modular and homogeneous decomposition.

The characterization of graphs totally decomposable by 1-decomposition is also given.

The last part of our paper is devoted to a generalization of the 1- decomposition.

We first show that some basic properties of modular decomposition can be extended in a new form of decomposition of graphs that we called operator decomposition.

We introduce the notion of a (P, Q)-module, where P and Q are hereditary graph-theoretic properties, the notion of a (P, Q)-split graph and the closed hereditary class (P, Q) of graphs (P and Q are closed under the operations of john of graphs and disjoint union of graphs, respectively).

On this base, we construct a special case of the operator decomposition that is called (P, Q)-decomposition.

Such decomposition is uniquely determined by an arbitrary minimal nontrivial (P, Q)-module in G.

In particular, if G ∉ (P, Q), then G has the unique canonical (P, Q)-decomposition.