The core of a graph (Q686290)

Let \(H= (V(H),E(H))\) and \(G= (V(G),E(G))\) be graphs which may be either directed or undirected but always finite. A homomorphism \(G\to H\) is a mapping \(f: V(G)\to V(H)\) such that \(gg'\in E(G)\) implies \(f(g)f(g')\in E(H)\). If \(H\) is a subgraph of \(G\) then a homomorphism \(G\to H\) such that \(f(h)= h\) for all \(h\in V(H)\) is called a retraction of \(G\) onto \(H\), and \(H\) a retract of \(G\). A subgraph \(H\) of \(G\) is called a core of \(G\) if there is a homomorphism \(G\to H\), but no homomorphism \(G\to H'\) for any proper subgraph \(H'\) of \(H\). It is easy to show that every finite graph has a core and that the core is unique. Furthermore, the core of a graph is its smallest retract. The main result of this paper is a proof that the problem of deciding whether a graph \(G\) is its own core is \({\mathcal N}{\mathcal P}\)-complete. It is also shown that it is \({\mathcal N}{\mathcal P}\)- complete to decide whether or not a graph is rigid, i.e., admits only the identity homomorphism to itself. Finally, the authors show that if the independence number of \(G\) is two, then problem of deciding whether \(G\) is a core becomes polynomially solvable, and they pose the problem of investigating the complexity of the core problem for graphs with independence number three.