An Upper Bound on the Basis Number of the Powers of the Complete Graphs

    loading  Checking for direct PDF access through Ovid


The basis number of a graph G is defined by Schmeichel to be the least integer h such that G has an h-fold basis for its cycle space. MacLane showed that a graph is planar if and only if its basis number is ≤ 2. Schmeichel proved that the basis number of the complete graph Kn is at most 3. We generalize the result of Schmeichel by showing that the basis number of the d-th power of Kn is at most 2d+1.

    loading  Loading Related Articles