# Article

Full entry | PDF   (0.2 MB)
Keywords:
\$P_3\$ intersection graph; connectivity; container; wide diameter
Summary:
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.
References:
[1] Broersma, H. J., Hoede, C.: Path graphs. J. Graph Theory 13 (1989), 427-444. DOI 10.1002/jgt.3190130406 | MR 1010578 | Zbl 0677.05068
[2] Chartrand, G., Lesniak, L.: Graphs and Digraphs, 4th edition. Chapman and Hall/CRC, Boca Raton, FL (2005). MR 2107429
[3] Du, D. Z., Hsu, D. F., Lyuu, Y. D.: On the diameter vulnerability of Kautz digraphs. Discrete Math. 151 (1996), 81-85. DOI 10.1016/0012-365X(94)00084-V | MR 1391254 | Zbl 0853.05043
[4] Ferrero, D.: Connectivity of path graphs. Acta. Math. Univ. Comen., New Ser. 72 (2003), 59-66. MR 2020578 | Zbl 1100.05056
[5] Hsu, L. H., Lin, C. K.: Graph Theory and Interconnection Networks. CRC Press, Boca Raton, FL (2008). MR 2454502
[6] Menon, Manju K., Vijayakumar, A.: The \$P_3\$ intersection graph. Util. Math. 75 (2008), 35-50. MR 2389697 | Zbl 1172.05045
[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 2657320
[8] Prisner, E.: Graph Dynamics. Pitman Research Notes in Mathematics Series 338, Longman, Essex, UK (1995). MR 1379114 | Zbl 0848.05001

Partner of