# Maximum Independent Sets Partition of (n,k)-Star Graphs

Authors: Fu-Tao Hu
Journal: Complexity
 (2019)

---

## Abstract

The(n,k)-star graph is a very important computer modelling. The independent number and chromatic number of a graph are two important parameters in graph theory. However, we have not known the values of these two parameters of the (n,k)-star graph since it was proposed. In this paper, we show a maximum independent sets partition of (n,k)-star graph. From that, we can immediately deduce the exact value of the independent number and chromatic number of (n,k)-star graph.


---

## Body

## 1. Introduction

For graph-theoretical notation and terminology not defined here, we follow [1]. In particular, let G=(V,E) be a simple undirected graph without loops and multiedges, where V=V(G) is thevertex set and E=E(G) is theedge set. If xy∈E(G), we call that two vertices x and y areadjacent. For a vertex x, all the vertices adjacent to it are theneighbors of x.A subsetS of V is said to be anindependent set if no two of vertices are adjacent in S of a graph G. The cardinality of a maximum independent set in a graph G is called theindependent number of G and is denoted by α(G). Let C be a set of k colours. A k-vertex-colouring (simply a k-colouring) is a mapping c:V→C such that any two adjacent vertices are assigned the different colours of graph G. A graph is k-colourable if it has a k-colouring. Thechromatic number, which is denoted by χ(G), is the minimum k, for which graph G is k-colourable.As we know, the interconnection networks take an important part in the parallel computing/communication systems. An interconnection network can be modeled by a graph, where the processors are the vertices and the edges are the communication links.In 1989, Akers and Krishnamurthy [2] introduced the n-dimensional star graph Sn, which has superior degree and diameter compared to the hypercube and it is highly hierarchical and symmetrical [3]. However, the vertex cardinality of the n-dimensional star is n!. The gap between n! and (n+1)! is very large when Sn is extended to Sn+1. Chiang and Chen [4] in 1995 generalized the star graph Sn to the (n,k)-star graph, which preserves many good properties of the star graph and has smaller scale. Since the (n,k)-star graph was introduced, it has received great attention in the literature [4–21].The independent number and chromatic number of a graph are two important parameters in graph theory. However, we did not know the values of these two parameters of the(n,k)-star graph as far as we know. In this paper, we show a maximum independent sets partition and determine the exact value of the independent number and chromatic number of (n,k)-star graph.


## 2. Preliminary Results

We use[n] to denote the set {1,2,…,n}, where n is a positive integer. Apermutation of [n] is a sequence of n distinct symbols of ui∈[n], u1u2…un. The n-dimensionalstar network, denoted by Sn, is a graph with the vertex set (1)VSn=u1u2…un:ui∈n,ui≠ujfori≠j.The edges are specified as follows:E ( S n ): u1u2…un is adjacent to v1v2…vn if there exists i with 2≤i≤n such that vj=uj for j∉{1,i}, v1=ui, and vi=u1.The star graphs are vertex-transitive(n-1)-regular of order n!.Letn and k be two positive integers with k∈[n-1], and let Γn,k be the set of all k-permutations on [n]; that is, Γn,k={p1p2…pk:pi∈[n]andpi≠pjfori≠j}. In 1995, Chiang and Chen [4] generalized the star graph to (n,k)-star graph denoted by Sn,k with vertex set V(Sn,k)=Γn,k. The adjacency is defined as follows: p1p2…pi…pk is adjacent to(1)pip2…p1…pk, where 2≤i≤k;(2)xp2…pi…pk, where x∈[n]\{pi:i∈[k]}.By definition,Sn,k is (n-1)-regular vertex-transitive with n!/(n-k)! vertices. Moreover, Sn,n-1≅Sn and Sn,1≅Kn, where Kn is the complete graph with order n.LetSn-1,k-1i denote a subgraph of Sn,k induced by all the vertices with the same last symbol i, for each i∈[n]. See Figure 1 for instance.Figure 1
The(4,2)-star graph S4,2.Lemma 1 (Chiang and Chen [4], 1995).
S n , k can be decomposed into n subgraphs Sn-1,k-1i, i∈[n], and each subgraph Sn-1,k-1i is isomorphic to Sn-1,k-1.Lemma 2 (Li and Xu [14], 2014).
For anyα=p2p3…pk∈Γn,k-1(k≥2), let Vα={p1α:p1∈[n],p1≠pi,2≤i≤k}. Then the subgraph of Sn,k induced by Vα is a complete graph of order n-k+1, denoted by Kn-k+1α.


## 3. Maximum Independent Sets Partition ofSn,k

Proposition 3.
The independent number ofSn,k is α(Sn,k)≤n!/(n-k+1)!.Proof.
This conclusion is true fork=1 since Sn,1≅Kn. Next, assume that k≥2. Let I be any maximum independent set of Sn,k. For any α=p2p3…pk∈Γn,k-1(k≥2), let Vα={p1α:p1∈[n],p1≠pi,2≤i≤k}. Then the subgraph of Sn,k induced by Vα is a complete graph of order n-k+1, denoted by Kn-k+1α by Lemma 2. Thus, I contains at most one vertex in Kn-k+1α. By definition, there are exactly n!/(n-k+1)! such Kn-k+1α. Therefore, α(Sn,k)=|I|≤n!/(n-k+1)!.Proposition 4.
LetI11={1},I21={2},…,In1={n}. Then {I11,I21,…,In1} is a maximum independent sets partition of Sn,1.Proposition 5.
Let(2)I12=21,32,43,…,nn-1,1n,I22=31,42,53,…,1n-1,2n,…In-12=n1,12,23,…,n-2n-1,n-1n.Then {I12,I22,…,In-12} is a maximum independent sets partition of Sn,2.For eachj∈[n-k+1], we use Ij2 of Sn-k+2,2 to generate a maximum independent set Ij3 of Sn-k+3,3. Step by step, we generate a maximum independent set Ijk of Sn,k in the following. For each i≥[k]\{1,2}, π∈Iji-1, and x∈[n-k+i-1], denote by π(x,n-k+i) a permutation that replaces x by n-k+i if x∈π (x∈π means x is equal to some symbol in π); otherwise π(x,n-k+i)=π. Let π=p1p2…pi be any vertex in Sn-k+i,i. Denote by π′=p2p1…pi the vertex by exchanging the first two symbols in π.Step  1. By Proposition 5, denoted by Ij2={(j+1)1,(j+2)2,…,(n-k+2)(n-k+2-j), 1(n-k+3-j), and 2(n-k+4-j),…,j(n-k+2)} is a maximum independent set of Sn-k+2,2 for each j∈[n-k+1].Step  2. Let Ij3(n-k+3)={π′(n-k+3):π∈Ij2} and Ij3(x)={π(x,n-k+3)x:π∈Ij2} for each x∈[n-k+2]. Let Ij3=⋃x∈[n-k+3]Ij3(x).… … …Step i-1. Let Iji(n-k+i)={π′(n-k+i):π∈Iji-1} and Iji(x)={π(x,n-k+i)x:π∈Iji-1} for each x∈[n-k+i-1]. Let Iji=⋃x∈[n]Iji(x).… … …Step k-1. Let Ijk(n)={π′n:π∈Ijk-1} and Ijk(x)={π(x,n)x:π∈Ijk-1} for each x∈[n-1]. Let Ijk=⋃x∈[n]Ijk(x).Letj∈[n-k+1] and i∈[k]\{1,2}. By the above construction, it is easy to see that Iji(x) is one corresponding to one with Iji-1 for each x∈[n-k+i] and Iji(x)∩Iji(x′)=∅ for every x′∈[n-k+i]\{x}. We can easily show the following conclusion by induction on i.Proposition 6.
For eachj∈[n-k+1] and i∈[k]\{1}, |Iji|=(n-k+i)!/(n-k+1)! and Iji∩Ij′i=∅ for any j′∈[n-k+1]\{j}. Therefore {I1i,I2i,…,In-k+1i} is a vertex sets partition of Sn-k+i,i.In the following, we show thatIji is an independent set of Sn-k+i,i for each i∈{3,4,…,k}, k≥3, and j∈[n-k+1].Lemma 7.
Leti∈{3,4,…,k}, k≥3, and j∈[n-k+1]. If Iji is an independent set of Sn-k+i,i, then Iji-1 is an independent set of Sn-k+i-1,i-1.Proof.
By Proposition5, Ij2 is an independent set of Sn-k+i-1,i-1 for each j∈[n-k+1]. Next assume that i≥4. Suppose to the contrary that Iji-1 is not an independent set of Sn-k+i-1,i-1. Firstly, assume that p1p2…ps…pi-1 and psp2…p1…pi-1 are two adjacent vertices in Iji-1 of Sn-k+i-1,i-1. If s=2, then p1(n-k+i)…pi-1p2 and (n-k+i)p1…pi-1p2 belong to Iji(p2)⊆Iji by the construction of Iji; the one to one correspondence is (3)p1p2…pi-1↔p1n-k+i…pi-1p2,p2p1…pi-1↔n-k+ip1…pi-1p2.However, p1(n-k+i)…pi-1p2 and (n-k+i)p1……pi-1p2 are adjacent in Sn-k+i,i, a contradiction. If s>2, then p1(n-k+i)…ps…pi-1p2 and ps(n-k+i)…p1…pi-1p2 belong to Iji(p2)⊆Iji by the construction of Iji; the one to one correspondence is (4)p1p2…ps…pi-1↔p1n-k+i…ps…pi-1p2,psp2…p1…pi-1↔psn-k+i…p1…pi-1p2.However, p1(n-k+i)…ps…pi-1p2 and ps(n-k+i)…p1…pi-1p2 are adjacent in Sn-k+i,i, a contradiction.
Secondly, assume thatp1p2…pi-1 and pip2…pi-1 are two adjacent vertices in Iji-1 of Sn-k+i-1,i-1. By the construction of Iji, p1(n-k+i)…pi-1p2 and pi(n-k+i)…pi-1p2 belong to Iji(p2)⊆Iji; the one to one correspondence is (5)p1p2…pi-1↔p1n-k+i…pi-1p2,pip2…pi-1↔pin-k+i…pi-1p2.
However,p1(n-k+i)…ps…pi-1p2 and pi(n-k+i)…ps…pi-1p2 are adjacent in Sn-k+i,i, a contradiction.Lemma 8.
Leti∈{3,…,k},  k≥3, and j∈[n-k+1]. If Iji-1 is an independent set of Sn-k+i-1,i-1, then the two vertices pπ1 and pπ2 can not both belong to Iji of Sn-k+i,i, where π1 and π2 are adjacent in Sn-k+i-1,i-1.Proof.
By Proposition5, Ij2={(j+1)1,(j+2)2,…,(n-k+2)(n-k+2-j), 1(n-k+3-j), and 2(n-k+4-j),…,j(n-k+2)} is an independent set of Sn-k+2,2.
We consider the case fori=3. Suppose to the contrary that there exist two vertices pπ1 and pπ2 in Ij3 but π1 and π2 are adjacent in Sn-k+2,2.
Assume thatπ1=p1p2 and π2=p2p1. Then pp1p2∈Ij3(p2) and pp2p1∈Ij3(p1). If p=n-k+3, then p2p1 and p1p2 are in Ij2 by the construction of Ij3; the one to one correspondence is (6)n-k+3p1p2↔p2p1,n-k+3p2p1↔p1p2.However, p2p1 and p1p2 are adjacent in Sn-k+2,2, a contradiction with Ij2 being an independent set of Sn-k+2,2. If p<n-k+3, then pp1 and pp2 are two vertices in Ij2 by the construction of Ij3; the one to one correspondence is (7)pp1p2↔pp1,pp2p1↔pp2,a contradiction with the construction of Ij2.
Now, assume thatπ1=p1p2 and π2=p3p2. Then pp1p2∈Ij3(p2) and pp3p2∈Ij3(p2). If p=n-k+3, then p2p1 and p2p3 are in Ij2 by the construction of Ij3; the one to one correspondence is (8)n-k+3p1p2↔p2p1,n-k+3p3p2↔p2p3,a contradiction with the construction of Ij2. If p<n-k+3, then pp1 and pp3 are two vertices in Ij2 by the construction of Ij3; the one to one correspondence is (9)pp1p2↔pp1,pp2p1↔pp2,a contradiction with the construction of Ij2.
Therefore, the conclusion is true fori=3.
We prove this Lemma by induction oni. Assume that the induction hypothesis is true for i-1 with i≥4. We prove the case for i≥4. Assume that Iji-1 is an independent set of Sn-k+i-1,i-1. Then Iji-2 is an independent set of Sn-k+i-2,i-2 by Lemma 7. Suppose to the contrary that there exist two vertices pπ1 and pπ2 in Iji but π1 and π2 are adjacent in Sn-k+i-1,i-1.
Firstly, assume thatπ1=p2p3…ps…pi-1pi and π2=psp3…p2…pi-1pi. Suppose that s=i. If p=n-k+i, then pip2p3…pi-1 and p2pip3…pi-1 are in Iji-1 by the construction of Iji; the one to one correspondence is (10)n-k+ip2p3…pi-1pi↔pip2p3…pi-1,n-k+ipip3…pi-1p2↔p2pip3…pi-1.However, pip2p3…pi-1 and p2pip3…pi-1 are adjacent in Sn-k+i-1,i-1, a contradiction.
Now assume thatp<n-k+i; then pp2p3…pi-1 and ppip3…pi-1 are two vertices in Iji-1 by the construction of Iji; the one to one correspondence is (11)pp2p3…pi-1pi↔pp2p3…pi-1,ppip3…pi-1p2↔ppip3…pi-1.However, p2p3…pi-1 and pip3…pi-1 are adjacent in Sn-k+i-2,i-2, a contradiction with the induction hypothesis.
Next, suppose thats≠i. If p=n-k+i, then pip2p3…ps…pi-1 and pipsp3…p2…pi-1 are two vertices in Iji-1 by the construction of Iji. Now assume that p<n-k+i. Then pp2p3…ps…pi-1 and ppsp3…p2…pi-1 are two vertices in Iji-1 by the construction of Iji. However, p2p3…ps…pi-1 and psp3…p2…pi-1 are two adjacent vertices in Sn-k+i-2,i-2, a contradiction with the induction hypothesis.
Secondly, assume thatπ1=p2p3…pi-1pi and π2=pi+1p3…pi-1pi. If p=n-k+i, then pip2p3…pi-1 and pipi+1p3…pi-1 are two vertices in Iji-1 by the construction of Iji. Now suppose that p<n-k+i. Then pp2p3…pi-1 and ppi+1p3…pi-1 are two vertices in Iji-1 by the construction of Iji. However, p2p3…pi-1 and pi+1p3…pi-1 are two adjacent vertices in Sn-k+i-2,i-2, a contradiction with the induction hypothesis.
By the principle of induction, this Lemma completes.Lemma 9.
Leti∈{3,…,k}, k≥3, and j∈[n-k+1]. If Iji-1 is an independent set of Sn-k+i,i, then Iji(x) is an independent set of Sn-k+i,i for each x∈[n-k+i].Proof.
Assume thati=3. Suppose to the contrary that Ij3(x) is not an independent set of Sn-k+3,3. Assume that p1p2x and p2p1x are two adjacent vertices in Ij3(x). By the construction of Ij3(x), p1p2,p2p1∈Ij2 if n-k+3∉{p1,p2} and xp2,p2x∈Ij2 if p1=n-k+3 (the case for p2=n-k+3 is similar), a contradiction with the construction of Ij2 in Proposition 5. Assume that p1p2x and p3p2x are two adjacent vertices in Ij3(x). By the construction of Ij3(x), we have (12)p2p1,p2p3∈Ij2,ifx=n-k+3,p1x,p3x∈Ij2,ifp2=n-k+3,xp2,p3p2∈Ij2,ifp1=n-k+3,p1p2,xp2∈Ij2,ifp3=n-k+3,p1p2,p3p2∈Ij2,otherwise.Any case above makes a contradiction with the construction of Ij2 in Proposition 5.
We proceed by induction oni≥3. Assume that the induction hypothesis is true for i-1 with i≥4. Next we prove that Iji(x) is an independent set of Sn-k+i,i for each x∈[n-k+i]. Suppose to the contrary that Iji(x) is not an independent set of Sn-k+i,i.
Firstly, assume thatp1p2…ps…pi-1x and psp2…p1…pi-1x are two adjacent vertices in Iji(x). On one hand, suppose that x=n-k+i. By the construction of Iji(n-k+i), we have (13)p2p1…ps…pi-1,p2ps…p1…pi-1∈Iji-1,ifs≥3,p2p1…pi-1,p1p2…pi-1∈Iji-1,ifs=2.The first case makes a contradiction with the result in Lemma 8, since p1p3…ps…pi-1 and psp3…p1…pi-1 are adjacent in Sn-k+i-2,i-2. The second case makes a contradiction with Iji-1 being an independent set. On the other hand, suppose that x<n-k+i. By the construction of Iji(x), we have p1p2…ps…pi-1,psp2…p1…pi-1∈Iji-1 if pt≠n-k+i for each t=1,2,…,i-1 (if pt=n-k+i, for some t∈{1,2,…,i}, we just replace pt by x). However, p1p2…ps…pi-1 and psp2…p1…pi-1 are adjacent in Sn-k+i-1,i-1, a contradiction with Iji-1 being an independent set.
Secondly, assume thatp1p2…pi-1x and pip2…pi-1x are two adjacent vertices in Iji(x). If x=n-k+i, then p2p1…pi-1 and p2pi…pi-1 are two vertices in Iji-1 by the construction of Iji(n-k+i). However, p1…pi-1 and pi…pi-1 are two adjacent vertices in Iji-2, a contradiction with the result in Lemma 8. Assume that x<n-k+i. By the construction of Iji(x), we have p1p2…pi-1,pip2…pi-1∈Iji-1 if pt≠n-k+i for each t=1,2,…,i-1,i (if pt=n-k+i, for some t∈{1,2,…,i}, we just replace pt by x). However, p1p2…pi-1 and pip2…pi-1 are adjacent in Sn-k+i-1,i-1, a contradiction with Iji-1 being an independent set.
By the principle of induction, this Lemma completes.Theorem 10.
The vertex setIji is an independent set of Sn-k+i,i for each j∈[n-k+1] and i∈{2,3,…,k}.Proof.
We proceed by induction oni≥2. By Proposition 5, Ij2 is an independent set of Sn-k+2,2. Assume that the induction hypothesis is true for i-1 with i≥3.
Assume thatIji-1 is an independent set of Sn-k+i-1,i-1. By Lemma 9, Iji(x) is an independent set of Sn-k+i,i for each x∈[n-k+i]. Suppose to the contrary that Iji is not independent. Assume that p1p2…pi-1pi and pip2…pi-1p1 are two adjacent vertices in Iji (this is the only possible case since Iji(x) is an independent set of Sn-k+i,i for each x∈[n-k+i]). If p1=n-k+i, then pip2…pi-1 and p2pi…pi-1 should be in Iji-1 by the construction of Iji, but they are two adjacent vertices in Iji-1, a contradiction (the case for pi=n-k+i is similar). If ps=n-k+i, for some s with 2≤s≤i-1, then p1p2…pi…pi-1 (replace n-k+i by pi) and pip2…p1…pi-1 (replace n-k+i by p1) should be in Iji-1 by the construction of Iji, but they are two adjacent vertices in Iji-1, a contradiction. Now assume that ps≠n-k+i for each s∈[i]. Then p1p2…pi-1 and pip2…pi-1 should be in Iji-1 by the construction of Iji, but they are two adjacent vertices in Iji-1, a contradiction. This Theorem completes.Theorem 11.
The constructedIjk is a maximum independent set of Sn,k for each j∈[n-k+1] and α(Sn,k)=n!/(n-k+1)!. Moreover, {I1k,I2k,…,In-k+1k} is a maximum independent sets partition of Sn,k.Proof.
By Proposition3, α(Sn,k)≤n!/(n-k+1)!. By Proposition 6, Ijk=n!/(n-k+1)!. By Theorem 10, Ijk is an independent set of Sn,k. Therefore, Ijk for each j∈[n-k+1] is a maximum independent set of Sn,k and α(Sn,k)=n!/(n-k+1)!. By Proposition 6, {I1k,I2k,…,In-k+1k} is a vertex sets partition of Sn,k, so {I1k,I2k,…,In-k+1k} is a maximum independent sets partition of Sn,k.Since{I1k,I2k,…,In-k+1k} is a maximum independent sets partition of Sn,k, we immediately obtain the chromatic number of Sn,k.Corollary 12.
The chromatic number ofSn,k is χ(Sn,k)=n-k+1.Next, we show the maximum independent sets partition ofS4,3 by our construction.Example 13 (see Figure2).
By Proposition5, I12={21,32,13} and I22={31,12,23} are two maximum independent sets of S3,2. The constructed two maximum independent sets of S4,3 are(14)I13=124,234,314∪241,321,431∪412,342,132∪213,423,143=I134∪I131∪I132∪I133,I23=134,214,324∪341,421,231∪312,142,432∪413,123,243=I234∪I231∪I232∪I233.Figure 2
The(3,2)-star graph S3,2 and the (4,3)-star graph S4,3.



---

*Source: 8247419-2019-07-04.xml*