Bipartite Theory of Graphs: Outer-Independent Domination

Let G = ( V , E ) be a bipartite graph with partite sets X and Y . Two vertices of X are X -adjacent if they have a common neighbor in Y , and they are X -independent otherwise. A subset D ⊆ X is an X -outer-independent dominating set of G if every vertex of X \ D has an X -neighbor in D , and all v...

Full description

Saved in:
Bibliographic Details
Published in:National Academy science letters 2015-04, Vol.38 (2), p.169-172
Main Authors: Krzywkowski, Marcin, Venkatakrishnan, Yanamandram B.
Format: Article
Language:English
Subjects:
History of Science
Humanities and Social Sciences
multidisciplinary
Science
Science (multidisciplinary)
Short Communication
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Let G = ( V , E ) be a bipartite graph with partite sets X and Y . Two vertices of X are X -adjacent if they have a common neighbor in Y , and they are X -independent otherwise. A subset D ⊆ X is an X -outer-independent dominating set of G if every vertex of X \ D has an X -neighbor in D , and all vertices of X \ D are pairwise X -independent. The X -outer-independent domination number of G , denoted by γ X o i ( G ) , is the minimum cardinality of an X -outer-independent dominating set of G . We prove several properties and bounds on the number γ X o i ( G ) .
ISSN:0250-541X
2250-1754
DOI:10.1007/s40009-014-0315-7