A characterization of star-perfect graphs

Title

A characterization of star-perfect graphs

Creator

Ravindra G.; Ghosh S.; Kureethara J.V.; Abraham V.M.

Description

Motivated by Berge perfect graphs, we define star-perfect graphs and characterize them. For a finite simple graph G(V, E), let (Formula presented.) denote the minimum number of induced stars contained in G such that the union of their vertex sets is V(G), and let (Formula presented.) denote the maximum number of vertices in G such that no two of them are contained in the same induced star of G. We call a graph G star-perfect if (Formula presented.), for every induced subgraph H of G. A graph G is star-perfect if and only if G is (Formula presented.) -free, for every (Formula presented.). A bipartite graph G is star-perfect if and only if every induced cycle in G is of length (Formula presented.). The minimum parameter (Formula presented.) and the maximum parameter (Formula presented.) have been extensively studied in various contexts. 2024 The Author(s). Published with license by Taylor & Francis Group, LLC.

Source

AKCE International Journal of Graphs and Combinatorics, Vol-21, No. 2, pp. 189-197.

Date

2024-01-01

Publisher

Taylor and Francis Ltd.

Subject

Perfect graph; star-imperfect graph; star-perfect graph

Coverage

Ravindra G., Department of Mathematics, CHRIST(Deemed to be University), Bengaluru, India; Ghosh S., Department of Mathematics, CHRIST(Deemed to be University), Bengaluru, India; Kureethara J.V., Department of Mathematics, CHRIST(Deemed to be University), Bengaluru, India; Abraham V.M., Department of Mathematics, CHRIST(Deemed to be University), Bengaluru, India

Rights

All Open Access; Gold Open Access

Relation

ISSN: 9728600

Format

Online

Language

English

Type

Article

Identifier

https://doi.org/10.1080/09728600.2024.2329927

https://www.scopus.com/inward/record.uri?eid=2-s2.0-85189801625&doi=10.1080%2f09728600.2024.2329927&partnerID=40&md5=444dc89528c0f9bb6f480ce5703b24f5