<abstract xmlns="http://www.w3.org/1999/xhtml">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) &lt; 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.</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.

Induced label graphoidal graphs

Department of Mathematics, The Madura College, Madurai-11

Department of Mathematics, Christ University, Bangalore-29 India

Acta Universitatis Sapientiae, Informatica

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

{"article-title":"Induced label graphoidal graphs"}

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...

Induced label graphoidal graphs

Published Online: Jan 27, 2015

Page range: 178 - 189

Received: Aug 12, 2014

DOI: https://doi.org/10.1515/ausi-2015-0002

© 2015

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.