×
Chen, Meirun; Guo, Xiaofeng; Zhai, Shaohui

The optimal strong radius and optimal strong diameter of the Cartesian product graphs. (English) Zbl 1209.05204

Appl. Math. Lett. 24, No. 5, 657-660 (2011).
Summary: Let \(D\) be a strong digraph. The strong distance between two vertices \(u\) and \(v\) in \(D\), denoted by \(sd_D(u,v)\), is the minimum size (the number of arcs) of a strong subdigraph of \(D\) containing \(u\) and \(v\). For a vertex \(v\) of \(D\), the strong eccentricity \(se(v)\) is the strong distance between \(v\) and a vertex farthest from \(v\). The minimum strong eccentricity among all vertices of \(D\) is the strong radius, denoted by \(srad(D)\), and the maximum strong eccentricity is the strong diameter, denoted by \(sdiam(D)\). The optimal strong radius (resp. strong diameter) \(srad(G)\) (resp. \(sdiam(G))\) of a graph \(G\) is the minimum strong radius (resp. strong diameter) over all strong orientations of \(G\). J. S.-T. Juan, C.-M. Huang and I-F. Sun [The strong distance problem on the Cartesian product of graphs,Inf. Process. Lett. 107, No. 2, 45–51 (2008; Zbl 1186.68022)] provided an upper and a lower bound for the optimal strong radius (resp. strong diameter) of the Cartesian products of any two connected graphs. In this work, we determine the exact value of the optimal strong radius of the Cartesian products of two connected graphs and a new upper bound for the optimal strong diameter. Furthermore, these results are also generalized to the Cartesian products of any \(n (n>2)\) connected graphs.

Cited in 1 Document

MSC:

05C76 Graph operations (line graphs, products, etc.)
05C20 Directed graphs (digraphs), tournaments

Keywords:

Cartesian product; optimal strong diameter; optimal strong radius; strong diameter; strong distance; strong radius

Citations:

Zbl 1186.68022
Cite Review PDF
Full Text: DOI

References:

[1] Chartrand, G.; Erwin, D.; Raines, M.; Zhang, P., Strong distance in strong digraphs, J. Combin. Math. Combin. Comput., 31, 33-44 (1999) · Zbl 0938.05029
[2] Juan, Justie Su-Tzu; Huang, Chun-Ming; Sun, I-Fan, The strong distance problem on the Cartesian product of graphs, Inform. Process. Lett., 107, 45-51 (2008) · Zbl 1186.68022
[3] Chen, Meirun; Guo, Xiaofeng; Li, Hao, Lower and upper orientable strong diameters of graphs satisfying the Ore condition, Appl. Math. Lett., 22, 994-997 (2009) · Zbl 1179.05038
[4] Dankelmann, Peter; Swart, Henda C.; Day, David P., On strong distance in oriented graphs, Discrete Math., 266, 195-201 (2003) · Zbl 1025.05020
[5] Juan, Justie Su-Tzu; Huang, Chun-Ming, On the strong distance problems of pyramid networks, Appl. Math. Comput., 195, 154-161 (2008) · Zbl 1135.68519
[6] Bang-Jensen, J.; Gutin, G., Digraphs: Theory, Algorithms and Applications (2000), Springer: Springer London
[7] Bondy, J. A.; Murty, U. S.R., Graph Theory with Applications (1976), The Macmillan Press Ltd. · Zbl 1134.05001
[8] Day, K.; Al-Ayyoub, A.-E., The cross product of interconnection networks, IEEE Trans. Parallel Distrib. Syst., 8, 2, 109-118 (1997)
[9] Imrich, Wilfried; Klavzar, Sandi, Product Graphs Structure and Recognition (2000), Wiley-Interscience Publication · Zbl 0963.05002
[10] Chen, Meirun; Guo, Xiaofeng, Lower and upper orientable strong radius and diameter of the Cartesian product of complete graphs, Ars Combin., 97, 175-182 (2010) · Zbl 1249.05161
[11] Huang, Yi; Chen, Meirun, Lower and upper orientable strong radius and diameter of the Cartesian product of paths, J. Xinjiang Univ. Natur. Sci. Ed., 26, 1, 33-37 (2009) · Zbl 1224.05143
[12] Robbins, H., A theorem on graphs with an application to a problem of traffic control, Amer. Math. Monthly, 46, 281-283 (1939) · JFM 65.0861.01
[13] Chiue, W.-S.; Shieh, B.-S., On connectivity of the Cartesian product of two graphs, Appl. Math. Comput., 102, 129-137 (1999) · Zbl 0927.05048
[14] Koh, K. M.; Tay, E. G., Optimal orientations of products of paths and cycles, Discrete Appl. Math., 78, 163-174 (1997) · Zbl 0886.05060
[15] Koh, K. M.; Tay, E. G., On optimal orientations of Cartesian products of even cycles, Networks, 32, 299-306 (1998) · Zbl 0990.05062
[16] Koh, K. M.; Tay, E. G., On optimal orientations of Cartesian products of trees, Graphs Combin., 17, 79-97 (2001) · Zbl 0984.05042
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.