A Study on Regular Perfect Graphs

Title

A Study on Regular Perfect Graphs

Creator

S Jayakumar, Gokul

Contributor

Shathish, Sangeetha

Description

A graph (V, E) is said to be a perfect graph if the independence number of every induced subgraph in G is equal to the clique covering number of the subgraph in G. The independence number of a graph G is denoted by and#945;(G), and it is the maximum number of vertices in G such that no two of them belong to the same clique in G. The clique covering number of a graph G is denoted by and#952;(G), and is the minimum number of cliques required to cover the vertex set of G. F- perfect graph is a special type of perfect graph, where F can be any graph, like, complete graph (Km), the complement of a complete graph (Km), star, cycle, and so on. A graph G is said to be F-perfect if F-independence number for every newlineinduced subgraph H of G is equal to its F-covering number. The F-independence number of a graph G is the maximum number of vertices in G such that no two of them belong to the same F-subgraph in G. F-covering number is the minimum number of F-subgraphs in G that is required to cover the vertex set of G. newlineThe present study introduces the concept of regular perfect graphs, and induced regular perfect graphs which are denoted by R-perfect graphs, and R-perfect graphs respectively. These graph classes are obtained by considering F as the set of all regular subgraphs in a graph, R, and the set of all induced regular subgraphs, R, in a graph respectively. We conceptualise the graph parameters, R-independence number, and R-covering number for R-perfect graphs and R-independence number, and R-covering number for R-perfect graphs, and characterise both these classes of graphs. We initially study a subclass of regular perfect graphs, namely, cycle perfect graphs (C-perfect graphs) and induced cycle perfect graphs (C-perfect graphs). Further we extend the study to analyse various product graphs under C-perfection, and characterise them.

Source

Author's Submission

Date

2024-01-01

Publisher

Christ(Deemed to be University)

Subject

Mathematics and Statistics

Rights

Open Access

Relation

61000362

Format

PDF

Language

English

Type

PhD

Identifier

http://hdl.handle.net/10603/585459