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.
Let G1 and G2 be copies of a graph G, and let f : V (G1) → V (G2) be a function. Then a functigraph C(G, f) = (V, E) is a generalization of a permutation graph, where V = V (G1) ∪ V (G2) and E = E(G1) ∪ E(G2) ∪ {uv : u ∈ V (G1), v ∈ V (G2), v = f(u)}. In this paper, we study colorability and planarity of functigraphs.