Induced label graphoidal graphs

Abstract

Let G be a non-trivial, simple, finite, connected and undirected graph of order n and size m. An induced acyclic graphoidal decomposition (IAGD) of G is a collection ψ of non-trivial and internally disjoint induced paths in G such that each edge of G lies in exactly one path of ψ. For a labeling f : V → {1, 2, 3, . . . ,n}, let ↑ Gf be the directed graph obtained by orienting the edges uv of G from u to v, provided f(u) < f(v). If the set ψf of all maximal directed induced paths in ↑ Gf with directions ignored is an induced path decomposition of G, then f is called an induced graphoidal labeling of G and G is called an induced label graphoidal graph. The number ηil = min{|ψf| : f is an induced graphoidal labeling of G} is called the induced label graphoidal decomposition number of G. In this paper we introduce and study the concept of induced graphoidal labeling as an extension of graphoidal labeling.

Keywords

• induced acyclic graphoidal decomposition
• induced label graphoidal graphs
• induced label graphoidal decomposition number