The search functionality is under construction.
The search functionality is under construction.

Keyword Search Result

[Keyword] chordal rings(2hit)

1-2hit
  • Completely Independent Spanning Trees on 4-Regular Chordal Rings

    Jou-Ming CHANG  Hung-Yi CHANG  Hung-Lung WANG  Kung-Jui PAI  Jinn-Shyong YANG  

     
    LETTER

      Vol:
    E100-A No:9
      Page(s):
    1932-1935

    Given a graph G, a set of spanning trees of G are completely independent spanning trees (CISTs for short) if for any vertices x and y, the paths connecting them on these trees have neither vertex nor edge in common, except x and y. Hasunuma (2001, 2002) first introduced the concept of CISTs and conjectured that there are k CISTs in any 2k-connected graph. Later on, this conjecture was unfortunately disproved by Péterfalvi (2012). In this note, we show that Hasunuma's conjecture holds for graphs restricted in the class of 4-regular chordal rings CR(n,d), where both n and d are even integers.

  • Completely Independent Spanning Trees on Some Interconnection Networks

    Kung-Jui PAI  Jinn-Shyong YANG  Sing-Chen YAO  Shyue-Ming TANG  Jou-Ming CHANG  

     
    LETTER-Information Network

      Vol:
    E97-D No:9
      Page(s):
    2514-2517

    Let T1,T2,...,Tk be spanning trees in a graph G. If, for any two vertices u,v of G, the paths joining u and v on the k trees are mutually vertex-disjoint, then T1,T2,...,Tk are called completely independent spanning trees (CISTs for short) of G. The construction of CISTs can be applied in fault-tolerant broadcasting and secure message distribution on interconnection networks. Hasunuma (2001) first introduced the concept of CISTs and conjectured that there are k CISTs in any 2k-connected graph. Unfortunately, this conjecture was disproved by Péterfalvi recently. In this note, we give a necessary condition for k-connected k-regular graphs with ⌊k/2⌋ CISTs. Based on this condition, we provide more counterexamples for Hasunuma's conjecture. By contrast, we show that there are two CISTs in 4-regular chordal rings CR(N,d) with N=k(d-1)+j under the condition that k ≥ 4 is even and 0 ≤ j ≤ 4. In particular, the diameter of each constructed CIST is derived.