Contents

\(K_2\)-Node Expansion Problems

Alfred Boals1, Naveed A. Sherwani1
1Department of Computer Science Western Michigan University Kalamazoo, MI 49008 U.S.A.

Abstract

In this paper, we introduce the concept of node expansion. Node expansion is a generalization of edge subdivision and an inverse of subgraph contraction. A graph \(G_1 = (V_1, E_1)\) is an \(H\)-node expansion of \(G = (V, E)\) if and only if \(G_1\) contains a subgraph \(H = (V_H, E_H)\) such that \(V = V_1 – V_H \cup \{v\}\) and \(E = E_1 – E_H \cup \{vw | wh \in E_1 \;\text{and}\; h \in V_H\} \cup \{v\}\). The concept of node expansion is of considerable importance in modernization of networks.

We consider the node expansion problem of transforming a graph to a bipartite graph with a minimum number of node expansions using \(K_2\). We show that the \(K_2\)-node expansion problem is NP-Complete for general graphs and remains so if the input graph has maximum degree 3. However, we present a \(O({n}^2 \log n + mn + p^3)\) algorithm for the case when the input graph is restricted to be planar \(3\)-connected and output graph is required to be planar bipartite.