Maximum independent sets in a proper monograph determined through a signature

被引：0

作者：

Hegde, S. M. ^{[1
]}

Saumya, Y. M. ^{[1
]}

机构：

[1] Natl Inst Technol Karnataka, Dept Math & Computat Sci, Surathkal 575025, India

来源：

DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS | 2023年 / 15卷 / 03期

关键词：

Proper monograph; signature; isolated vertices; working vertices; independent sets;

D O I：

10.1142/S1793830922500926

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

Let G = (V,E) be a non-empty, finite graph. If the vertices of G can be bijectively labeled by a set S of positive distinct real numbers with two vertices being adjacent if and only if the positive difference of the corresponding labels is in S, then G is called a proper monograph. The set S is called the signature of G and denoted as G(S). Not all proper monographs have the property that a set of idle vertices can be bijectively mapped to the maximum independent sets. As a result, in this paper, we present the proper monograph labelings of several classes of graphs that satisfy the property mentioned above. We present the proper monograph labelings of graphs such as cycles, C-n circle dot K-1, cycles with paths attached to one or more vertices, and Cycles with an irreducible tree attached to one or more vertices.

引用

页数：13