Article ID Journal Published Year Pages File Type
4647279 Discrete Mathematics 2014 15 Pages PDF
Abstract

Given a graph GG, a subset MM of V(G)V(G) is a module   of GG if for each v∈V(G)∖Mv∈V(G)∖M, vv is adjacent to all the elements of MM or to none of them. A graph GG is prime   if |V(G)|≥4|V(G)|≥4 and the only modules of GG are V(G)V(G), 0̸0̸, and singleton vertex sets. Given a prime induced subgraph G[X]G[X], we introduce a digraph that yields a necessary and sufficient condition for GG to be prime.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,