Back close

Further results on set-valued graphs

Publication Type : Journal Article

Publisher : Journal of Discrete Mathematical Sciences and Cryptography

Source : Journal of Discrete Mathematical Sciences and Cryptography, Taylor & Francis, Volume 11, Issue 5, Number 5, p.559–566 (2008)

Url :

Campus : Coimbatore

School : School of Engineering

Department : Mathematics

Year : 2008

Abstract : Acharya [2] introduced the notion of set-valuation as: G=(V, E) be a (p, q) graph, X be a nonempty set of cardinality n and 2 X denote the set of all subsets of X. A set-indexer of G is an injective set-valued function f : V(G) → 2 X such that the function f ⊕: E(G) → 2 X −{∅} defined by f ⊕(uv)=f (v) ⊕ f (v) for every uv∈E(G) is also injective, where ⊕ is the symmetric difference of sets. A(p,q)-graph G=(V,E) is set-graceful if it admits a set-graceful labeling which is a set-valued injection f: V→2 X such that the function f ⊕ : E → 2 X defined by f ⊕ (uv)=f (u) ⊕ f (u) for all uv∈E is such that f ⊕ (E) ≔ {f ⊕(uv) : uv∈E}=2 X −{∅} and set-sequential if it admits a set-valued injection f : V∪E → 2 X , called a set-sequential labeling of G, such that f (V∪E) ≔ {f (x) : x∈V∪E}=2 X −{∅}. In this paper, we contribute two new necessary conditions for a graph to be set-sequential. In addition, we characterize stars that are set-sequential and also establish that certain specifically structured trees such as binary trees and bistars are not set-sequential. Also we prove that wheel is not set-sequential. Acharya in a personal communication to the first author in April 2007 during her visit to ISI, Delhi conjectured that “Tree TP obtained by pegging the whole of a binary tree T to a pivot P through an extra edge, called the hanger, joining P to the ‘top’ vertex of T (which is its centre as such), the new tree TP is set-sequential!”. We prove the conjecture for uniform binary trees.

Cite this Research Publication : K. A. Germina, Abhishek, K., and Princy, K. L., “Further results on set-valued graphs”, Journal of Discrete Mathematical Sciences and Cryptography, vol. 11, no. 5, pp. 559–566, 2008.

Admissions Apply Now