99-16: Characterizations of Consistent Marked Graphs

DIMACS TR: 99-16

Characterizations of Consistent Marked Graphs

Authors: Fred S. Roberts and Shaoji Xu

ABSTRACT
A marked graph is a graph with a + or - sign on each vertex and is called consistent if each cycle has an even number of - signs. This concept is motivated by problems of communication networks and social networks. We present some new characterizations/recognition algorithms for consistent marked graphs.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1999/99-16.ps.gz

DIMACS Home Page