Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
$P_3$ intersection graph; connectivity; container; wide diameter
$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
Search
Partner of
