Name
Abstract | ||
|---|---|---|
Let S⊆V(G) and κG(S) denote the maximum number k of edge-disjoint trees T1,T2,…,Tk in G such that V(Ti)⋂V(Tj)=S for any i,j∈{1,2,…,k} and i≠j. For an integer r with 2≤r≤n, the generalizedr-connectivity of a graph G is defined as κr(G)=min{κG(S)|S⊆V(G) and |S|=r}. The r-component connectivity cκr(G) of a non-complete graph G is the minimum number of vertices whose deletion results in a graph with at least r components. These two parameters are both generalizations of traditional connectivity. Except hypercubes and complete bipartite graphs, almost all known κr(G) are about r=3. In this paper, we focus on κ4(Dn) of dual cube Dn. We first show that κ4(Dn)=n−1 for n≥4. As a corollary, we obtain that κ3(Dn)=n−1 for n≥4. Furthermore, we show that cκr+1(Dn)=rn−r(r+1)2+1 for n≥2 and 1≤r≤n−1. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1016/j.dam.2018.09.025 | Discrete Applied Mathematics |
Keywords | Field | DocType |
Generalized connectivity,Component connectivity,Fault-tolerance,Dual cube | Integer,Graph,Discrete mathematics,Combinatorics,Vertex (geometry),Bipartite graph,Mathematics,Hypercube,Cube | Journal |
Volume | ISSN | Citations |
257 | 0166-218X | 1 |
PageRank | References | Authors |
0.35 | 12 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Shu-Li Zhao | 1 | 1 | 4.40 |
| Rongxia Hao | 2 | 165 | 26.11 |
| Eddie Cheng | 3 | 291 | 33.47 |