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.
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 myris@myris.cz.
