The P3 intersection graph of a graph G has for vertices all the induced paths of order 3 in G. Two vertices in P3(G) are adjacent if the corresponding paths in G are not disjoint. A w-container between two different vertices u and v in a graph G is a set of w internally vertex disjoint paths between u and v. The length of a container is the length of the longest path in it. The w-wide diameter of G is the minimum number l such that there is a w-container of length at most l between any pair of different vertices u and v in G. Interconnection networks are usually modeled by graphs. The w-wide diameter provides a measure of the maximum communication delay between any two nodes when up to w − 1 nodes fail. Therefore, the wide diameter constitutes a measure of network fault tolerance. In this paper we construct containers in P3(G) and apply the results obtained to the study of their connectivity and wide diameters.
The paper deals with graph operators-the Gallai graphs and the anti-Gallai graphs. We prove the existence of a finite family of forbidden subgraphs for the Gallai graphs and the anti-Gallai graphs to be H-free for any finite graph H. The case of complement reducible graphs-cographs is discussed in detail. Some relations between the chromatic number, the radius and the diameter of a graph and its Gallai and anti-Gallai graphs are also obtained.