Geodesic
Containers and wide diameters of $P_3(G)$
Mathematica Bohemica, Tome 137 (2012) no. 4, pp. 383-393

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

MR Zbl
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.
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.
DOI : 10.21136/MB.2012.142994
Classification : 05C38, 05C40, 05C76, 05C99
Keywords: $P_3$ intersection graph; connectivity; container; wide diameter 
Ferrero, Daniela; Menon, Manju K.; Vijayakumar, A. Containers and wide diameters of $P_3(G)$. Mathematica Bohemica, Tome 137 (2012) no. 4, pp. 383-393. doi: 10.21136/MB.2012.142994
@article{10_21136_MB_2012_142994,
     author = {Ferrero, Daniela and Menon, Manju K. and Vijayakumar, A.},
     title = {Containers and wide diameters of $P_3(G)$},
     journal = {Mathematica Bohemica},
     pages = {383--393},
     year = {2012},
     volume = {137},
     number = {4},
     doi = {10.21136/MB.2012.142994},
     mrnumber = {3058270},
     zbl = {1274.05255},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/MB.2012.142994/}
}
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
SP  - 383
EP  - 393
VL  - 137
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.21136/MB.2012.142994/
DO  - 10.21136/MB.2012.142994
LA  - en
ID  - 10_21136_MB_2012_142994
ER  - 
%0 Journal Article
%A Ferrero, Daniela
%A Menon, Manju K.
%A Vijayakumar, A.
%T Containers and wide diameters of $P_3(G)$
%J Mathematica Bohemica
%D 2012
%P 383-393
%V 137
%N 4
%U http://geodesic.mathdoc.fr/articles/10.21136/MB.2012.142994/
%R 10.21136/MB.2012.142994
%G en
%F 10_21136_MB_2012_142994

[1] Broersma, H. J., Hoede, C.: Path graphs. J. Graph Theory 13 (1989), 427-444. | DOI | MR | Zbl

[2] Chartrand, G., Lesniak, L.: Graphs and Digraphs, 4th edition. Chapman and Hall/CRC, Boca Raton, FL (2005). | MR

[3] Du, D. Z., Hsu, D. F., Lyuu, Y. D.: On the diameter vulnerability of Kautz digraphs. Discrete Math. 151 (1996), 81-85. | DOI | MR | Zbl

[4] Ferrero, D.: Connectivity of path graphs. Acta. Math. Univ. Comen., New Ser. 72 (2003), 59-66. | MR | Zbl

[5] Hsu, L. H., Lin, C. K.: Graph Theory and Interconnection Networks. CRC Press, Boca Raton, FL (2008). | MR

[6] Menon, Manju K., Vijayakumar, A.: The $P_3$ intersection graph. Util. Math. 75 (2008), 35-50. | MR | Zbl

[7] Menon, Manju K., Vijayakumar, A.: The dynamics of the $P_3$ intersection graph. J. Combin. Math. and Combin. Comput. 73 (2010), 127-134. | MR

[8] Prisner, E.: Graph Dynamics. Pitman Research Notes in Mathematics Series 338, Longman, Essex, UK (1995). | MR | Zbl

Cité par Sources :