• DocumentCode
    3622105
  • Title

    Fault-diameter of generalized Cartesian products

  • Author

    I. Banic;J. Zerovnik

  • Author_Institution
    FME, University of Maribor, Slovenia
  • fYear
    2006
  • fDate
    6/28/1905 12:00:00 AM
  • Firstpage
    3
  • Lastpage
    3
  • Abstract
    Cartesian graph bundles is a class of graphs that is a generalization of the Cartesian graph products. Let G be a kG-connected graph and D_c(G) denote the diameter of G after deleting any of its c \lt kG vertices. For a product of three factors G_1, G_2 and G_3, we prove that D_a+b+c+2(G) \lt D_a(G_1) + D_b(G_2) + D_c(G_3) + 1. We indicate how analogous proof gives the upper bound D_a+b+1(G) \lt D_a(G_1) + D_b(G_2) + 1 for the product of two factors. Finally, we show that D_a+b+1(G) \lt D_a(F) + D_b(B)+1 if G is a graph bundle with fibre F over base B, a \lt k_F,and b \lt k_B.
  • Keywords
    "Upper bound","Network topology","Multiprocessor interconnection networks","Hypercubes","Mathematics","Physics","Delay","Context","Communication networks","Fault tolerance"
  • Publisher
    ieee
  • Conference_Titel
    Distributed Computing Systems Workshops, 2006. ICDCS Workshops 2006. 26th IEEE International Conference on
  • ISSN
    1545-0678
  • Print_ISBN
    0-7695-2541-5
  • Type

    conf

  • DOI
    10.1109/ICDCSW.2006.51
  • Filename
    1648891