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:; Manju K. Menon, Department of Mathematics, St. Paul's College, Kalamassery, Kerala, India, e-mail:; A. Vijayakumar, Department of Mathematics, Cochin University of Science and Technology, Cochin-682022, India, e-mail:

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.

Access to the full text of journal articles on this site is restricted to the subscribers of Myris Trade. To activate your access, please contact Myris Trade at

[Previous Article] [Next Article] [Contents of This Number] [Contents of Mathematica Bohemica]
[Full text of the older issues of Mathematica Bohemica at DML-CZ]