MATHEMATICA BOHEMICA, Vol. 137, No. 4, pp. 383-393, 2012

# Containers and wide diameters of \$P_3(G)\$

## Daniela Ferrero, Manju K. Menon, A. Vijayakumar

Daniela Ferrero, Department of Mathematics, Texas State University, San Marcos, TX 78666, USA, e-mail: dferrero@txstate.edu; Manju K. Menon, Department of Mathematics, St. Paul's College, Kalamassery, Kerala, India, e-mail: manjumenonk@gmail.com; A. Vijayakumar, Department of Mathematics, Cochin University of Science and Technology, Cochin-682022, India, e-mail: vijay@cusat.ac.in

Abstract: The \$P_3\$ intersection graph of a graph \$G\$ has for vertices all the induced paths of order 3 in \$G\$. Two vertices in \$P_3(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 \$P_3 (G)\$ and apply the results obtained to the study of their connectivity and wide diameters.

Keywords: \$P_3\$ intersection graph, connectivity, container, wide diameter

Classification (MSC 2010): 05C40, 05C76, 05C99

Full text available as PDF.