Manimuthu Yamuna and Kumarasamy Karthika

DOI: 10.14456/sjst-psu.2018.47

pp. 333 - 338

Abstract

Let G₁ and G₂ be two undirected graphs, (v w) be an edge of G₁, and (x y) be an edge of G₂. 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 G₁ and G₂. We have obtained a necessary and sufficient
condition for graphs G₁ and G₂ to be Hajos stable.

Keywords

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