Name
Abstract | ||
|---|---|---|
The induced matching partition number of a graph G, denoted by imp(G), is the minimum integer k such that V(G) has a k-partition (V1, V2 … Vk ) such that, for each i, 1 ≤ i ≤ k, G(Vi), the subgraph of G induced by Vi, is a 1-regular graph. The induced matching k-partition problem is NP-complete even for k = 2. In this paper we investigate the induced matching partition problem for butterfly networks. We identify hypercubes, cube-connected cycles, grids of order m x n, where at least one of m and n is even, as graphs for which imp(G) = 2. In the sequel we prove that imp(G) does not exist for grids of order m x n where m and n are both odd and Mesh of trees MT(n), n ≥ 2. |
Year | Venue | Keywords |
|---|---|---|
2006 | FCS | partition,matching,mesh of trees,induced graph,butterfly networks,cube connected cycles,regular graph |
Field | DocType | Citations |
Integer,Partition problem,Discrete mathematics,Graph,Combinatorics,Folded cube graph,Interconnection,Partition (number theory),Mathematics,Hypercube | Conference | 0 |
PageRank | References | Authors |
0.34 | 4 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Paul Manuel | 1 | 221 | 17.42 |
| Indra Rajasingh | 2 | 193 | 24.17 |
| Bharati Rajan | 3 | 135 | 12.91 |
| Albert Muthumalai | 4 | 4 | 1.45 |