Structural Properties of Super Strongly Perfect Graphs

Abstract

Graph theory is one of the oldest and prominent mathematical disciplines with potential newlineapplications in the fields like operation research, social science and computer newlinescience. Graphs are applied to model pairwise relationships among objects. Considering newlinesome natural justifications, hereditary properties in graphs play a significant newlinerole related to its structure and applicability. Various families of perfect graphs were newlineintroduced in the literature, stimulated by the appealing hereditary features of all induced newlinesubgraphs of a given graph. Depending on divergent hereditary characteristics newlineof induced subgraphs, graphs are principally classified as perfect, strongly perfect, newlinesuper strongly perfect, trivially perfect and very strongly perfect. Perfect and strongly newlineperfect graphs have been broadly investigated. Super strongly perfect graphs handle newlinethe concepts of minimal dominating sets and maximal complete subgraphs. newlineThe principal objective of this work is to study the structural properties of super newlinestrongly perfect graphs. It is proved that several kinds of graphs are having the nature newlineof super strongly perfectness. Paths, even cycles, trees and complete graphs are newlineconfirmed to be super strongly perfect. Errors in few existing results are identified newlineand alternative acceptable conclusions are developed with suitable proofs. Existing newlinecharacterizations for these graphs are disproved with certain counter examples. The newlineauthors have found that odd cycles of length at least five, complements of cycles of newlinelength at least six, some special non isomorphic graphs and their odd refinements are newlineall non-super strongly perfect. It is also established that if a graph G accommodates newlinean odd cycle of length at least five, then its line graph L(G) need not be super newlinestrongly perfect. The relationships between different families of perfect graphs are newlinealso provided.Further, different graph operations like Cartesian product, tensor product and newlinesymmetrical difference on super strongly perfect graphs are discussed.