Containers and wide diameters of $P_3\left(G\right)$

Ferrero, Daniela, Menon, Manju K., and Vijayakumar, A.. "Containers and wide diameters of $P_3(G)$." Mathematica Bohemica 137.4 (2012): 383-393. <http://eudml.org/doc/247229>.

@article{Ferrero2012,
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.},
author = {Ferrero, Daniela, Menon, Manju K., Vijayakumar, A.},
journal = {Mathematica Bohemica},
keywords = {$P_3$ intersection graph; connectivity; container; wide diameter; container; connectivity; -graph},
language = {eng},
number = {4},
pages = {383-393},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Containers and wide diameters of $P_3(G)$},
url = {http://eudml.org/doc/247229},
volume = {137},
year = {2012},
}

TY - JOUR
AU - Ferrero, Daniela
AU - Menon, Manju K.
AU - Vijayakumar, A.
TI - Containers and wide diameters of $P_3(G)$
JO - Mathematica Bohemica
PY - 2012
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 137
IS - 4
SP - 383
EP - 393
AB - 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.
LA - eng
KW - $P_3$ intersection graph; connectivity; container; wide diameter; container; connectivity; -graph
UR - http://eudml.org/doc/247229
ER -