Wide-diameter of Product Graphs

• Autorzy: Erveš R. , Žerovnik J.
• Języki publikacji: EN

Abstrakty

EN

The product graph B * F of graphs B and F is an interesting model in the design of large reliable networks. Fault tolerance and transmission delay of networks are important concepts in network design. The notions are strongly related to connectivity and diameter of a graph, and have been studied by many authors. Wide diameter of a graph combines studying connectivity with the diameter of a graph. Diameter with width k of a graph G, k-diameter, is defined as the minimum integer d for which there exist at least k internally disjoint paths of length at most d between any two distinct vertices in G. Denote by D^W_c the c-diameter of G and κ(G) the connectivity of G. We prove that D^W_a+b(B * F) £ ra(F) + D^W_b (B) + 1 for a ≤ κ(F) and b ≤ κ(B). The Rabin number rc(G) is the minimum integer d such that there are c internally disjoint paths of length at most d from any vertex v to any set of c vertices {v1, v2, ... , vc}.

Słowa kluczowe

EN

Cartesian graph bundle; fault diameter; product graph; Rabin number; Wide-diameter

• Wydawca: Polskie Towarzystwo Matematyczne
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2013
• Tom: Vol. 125, nr 2
• Strony: 153--160
• Opis fizyczny: Bibliogr. 19 poz.

Twórcy

autor

Erveš R.

• FCE, University of Maribor, Smetanova 17, Maribor 2000, Slovenia

autor

Žerovnik J.

• FME, University of Ljubljana, Aškerčeva 6, Ljubljana 1000, Slovenia

Bibliografia

• [1] I. Banic, J. Zerovnik: Fault-diameter of Cartesian graph bundles, Information Processing Letters, 100, 2006, 47-51.
• [2] I. Banic, R. Erves, J. Zerovnik: The Edge fault-diameter of Cartesian graph bundles, European Journal of Combinatorics 30, 2009, 1054-1061.
• [3] I. Banic, R. Erves, J. Zerovnik: Edge, vertex and mixed fault diameters, Advances in Applied Mathematics 43, 2009, 231-238.
• [4] I. Banic, J. Zerovnik: Wide-diameter of Cartesian graph bundles, Discrete Mathematics 310, 2010, 16971701.
• [5] J.-C. Bermond, C. Delorme, G. Farh: Large graphs with given degree and diameter II, Journal of Combinatorial Theory B 36, 1984, 32-48.
• [6] G. Chatrand, F. Harary: Planar permutation graphs, Annales de l’Institut Poincare Sec. B 3 , 1967, 433-438.
• [7] P. Cull, S. M. Larson: On generalized twisted cubes, Information Processing Letters, 55 , 1995, 53-55.
• [8] K. Efe: A variation on the hypercube with lower diameter, IEEE Transactions on Computers 40 , 1991, 1312-1316.
• [9] S-Y. Hsieh and Y-S. Chen: Strongly Diagnosable Product Networks Under the Comparison Diagnosis Model, IEEE Transactions on Computers 57, 2008, 721-732.
• [10] S-Y. Hsieh, T-Y. Chuang: The Strong Diagnosability of Regular Networks and Product Networks under the PMC Model, IEEE Transactions on Parallel and Distributed Systems 20 , 2009, 367-378.
• [11] W. Imrich, S. KlavZar: Products Graphs, Structure and Recognition, Wiley, New York, 2000.
• [12] T. Kojima and K. Ando: Wide-diameter and minimum length of fan, Theoretical Computer Science 235, 2000, 257-266.
• [13] T. Kojima: Wide diameter and minimum length disjoint Menger path systems, Networks 46,2005, 136-141.
• [14] T. Kojima: On strong Rabin numbers of graphs and digraphs, Advances and Applications of Discrete Mathematics 3, 2009, 85-108.
• [15] S. C. Liawd, G. J. Chang, Generalized Diameters and Rabin Numbers of Networks, Journal of Combinatorial Optimization 2, 1999, 371-384.
• [16] T. Pisanski, J. Shawe-Taylor, J. Vrabec: Edge-colorability of graph bundles, Journal of Combinatorial Theory B 35, 1983, 12-19.
• [17] I. StojmenoviC: Multiplicative circulant networks: Topological properties and communication algorithms, Discrete Applied Mathematics 77, 1997, 281-305.
• [18] M. Xu, J.-M. Xu, X.-M. Hou: Fault diameter of Cartesian product graphs, Information Processing Letters 93, 2005, 245-248.
• [19] J.-M. Xu, C. Yang: Fault diameter of product graphs, Information Processing Letters 102, 2007, 226-228.