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