Hajos stable graphs

Abstract

Let G1 and G2 be two undirected graphs, (v w) be an edge of G1, and (x y) be an edge of G2. Hajos construction forms a new graph H, that combines the two graphs by identifying vertices v and x into a single vertex, removing the two edges (v w) and (x y), and adding a new edge (w y). In this paper we introduce a new kind of graph called the Hajos stable graph, where the stable property is defined using the domination number of graphs G1 and G2. We have obtained a necessary and sufficient condition for graphs G1 and G2 to be Hajos stable.

Keywords

• domination number
• Hajos construction
• Hajos graph
• stable graph