| Title:
|
Containers and wide diameters of $P_3(G)$ (English) |
| Author:
|
Ferrero, Daniela |
| Author:
|
Menon, Manju K. |
| Author:
|
Vijayakumar, A. |
| Language:
|
English |
| Journal:
|
Mathematica Bohemica |
| ISSN:
|
0862-7959 (print) |
| ISSN:
|
2464-7136 (online) |
| Volume:
|
137 |
| Issue:
|
4 |
| Year:
|
2012 |
| Pages:
|
383-393 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
$P_3$ intersection graph |
| Keyword:
|
connectivity |
| Keyword:
|
container |
| Keyword:
|
wide diameter |
| MSC:
|
05C38 |
| MSC:
|
05C40 |
| MSC:
|
05C76 |
| MSC:
|
05C99 |
| idZBL:
|
Zbl 1274.05255 |
| idMR:
|
MR3058270 |
| DOI:
|
10.21136/MB.2012.142994 |
| . |
| Date available:
|
2012-11-10T20:25:10Z |
| Last updated:
|
2020-07-29 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/142994 |
| . |
| Reference:
|
[1] Broersma, H. J., Hoede, C.: Path graphs.J. Graph Theory 13 (1989), 427-444. Zbl 0677.05068, MR 1010578, 10.1002/jgt.3190130406 |
| Reference:
|
[2] Chartrand, G., Lesniak, L.: Graphs and Digraphs, 4th edition.Chapman and Hall/CRC, Boca Raton, FL (2005). MR 2107429 |
| Reference:
|
[3] Du, D. Z., Hsu, D. F., Lyuu, Y. D.: On the diameter vulnerability of Kautz digraphs.Discrete Math. 151 (1996), 81-85. Zbl 0853.05043, MR 1391254, 10.1016/0012-365X(94)00084-V |
| Reference:
|
[4] Ferrero, D.: Connectivity of path graphs.Acta. Math. Univ. Comen., New Ser. 72 (2003), 59-66. Zbl 1100.05056, MR 2020578 |
| Reference:
|
[5] Hsu, L. H., Lin, C. K.: Graph Theory and Interconnection Networks.CRC Press, Boca Raton, FL (2008). MR 2454502 |
| Reference:
|
[6] Menon, Manju K., Vijayakumar, A.: The $P_3$ intersection graph.Util. Math. 75 (2008), 35-50. Zbl 1172.05045, MR 2389697 |
| Reference:
|
[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 |
| Reference:
|
[8] Prisner, E.: Graph Dynamics.Pitman Research Notes in Mathematics Series 338, Longman, Essex, UK (1995). Zbl 0848.05001, MR 1379114 |
| . |
