Integral sum graphs G_n and G_-r,n are perfect graphs

Abstract

A graph G is an integral sum graph (sum graph) if its vertices can be labeled with distinct integers (positive integers) so that e = uv is an edge of G if and only if the sum of the labels on vertices u and v is also a label in G. A graph G is perfect if the chromatic number of each of its induced subgraphs is equal to the clique number of the same. A simple graph G is of class 1 if its edge chromatic number and maximum degree are same. In this paper, we prove that integral sum graphs G_n, $G_{0,n}$ and $G_{-r,n}$ over the label sets $[1,n],[0,n]$ and $[-r,n]$, respectively, are perfect graphs as well as of class 1 for $r,n\in \mathbb{N}$. We also obtain a few structural properties of these graphs.

Keywords:

• Integral sum graph
• covering number
• independence number
• chromatic number
• clique number
• perfect graphs

2010MATHEMATICS SUBJECT CLASSIFICATION:

• 05C78
• 05C15
• 05C17
• 05C99

Acknowledgments

The first, second and fourth authors express their sincere gratitude to the Central University of Kerala, Periye, Kasaragod - 671316, Kerala, India for providing facilities to carry out this research work. Also, the authors are thankul to the anonymous reviewers for their valuable comments and suggestions to improve the presentation of the paper.

Disclosure statement

The authors declare that there is no conflict of interests regarding the publication of this paper.

Additional information

Funding

The first author would like to acknowledge her gratitude to the University Grants Commission (UGC), India, for providing financial support in the form of Junior Research fellowship (Ref. No.: 19/06/2016(i)EU-V). The second author would like to acknowledge her gratitude to the Council of Scientific and Industrial Research (CSIR), India, for the financial support under the CSIR Junior Research Fellowship scheme.