Characterizations of consistent marked graphs

Fred S. Roberts; Shaoji Xu

doi:10.1016/S0166-218X(02)00254-8

Characterizations of consistent marked graphs

Fred S. Roberts, Shaoji Xu

Institute for Quantitative Biomedicine (IQB)

Research output: Contribution to journal › Article › peer-review

11 Scopus citations

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 and recognition algorithms for consistent marked graphs.

Original language	English (US)
Pages (from-to)	357-371
Number of pages	15
Journal	Discrete Applied Mathematics
Volume	127
Issue number	2 SPEC.
DOIs	https://doi.org/10.1016/S0166-218X(02)00254-8
State	Published - Apr 15 2003

All Science Journal Classification (ASJC) codes

Discrete Mathematics and Combinatorics
Applied Mathematics

Access to Document

10.1016/S0166-218X(02)00254-8

Cite this

@article{0c9bafda206d4b51bb8bdfa4ae732a63,

title = "Characterizations of consistent marked graphs",

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 and recognition algorithms for consistent marked graphs.",

author = "Roberts, {Fred S.} and Shaoji Xu",

note = "Funding Information: Fred Roberts thanks the National Science Foundation for its support under grant NSF-SBR-9709134 to Rutgers University and Paul Dreyer for his helpful comments. Shaoji Xu thanks the Air Force Office of Scientific Research and the National Science Foundation for their support under grants AFOSR-89-0066, AFOSR-90-0008, AFOSR-F49620-93-1-0041, NSF-SBR-9211492 and NSF-SBR-9709134 to Rutgers University.",

year = "2003",

month = apr,

day = "15",

doi = "10.1016/S0166-218X(02)00254-8",

language = "English (US)",

volume = "127",

pages = "357--371",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

number = "2 SPEC.",

}

TY - JOUR

T1 - Characterizations of consistent marked graphs

AU - Roberts, Fred S.

AU - Xu, Shaoji

N1 - Funding Information: Fred Roberts thanks the National Science Foundation for its support under grant NSF-SBR-9709134 to Rutgers University and Paul Dreyer for his helpful comments. Shaoji Xu thanks the Air Force Office of Scientific Research and the National Science Foundation for their support under grants AFOSR-89-0066, AFOSR-90-0008, AFOSR-F49620-93-1-0041, NSF-SBR-9211492 and NSF-SBR-9709134 to Rutgers University.

PY - 2003/4/15

Y1 - 2003/4/15

N2 - 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 and recognition algorithms for consistent marked graphs.

AB - 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 and recognition algorithms for consistent marked graphs.

UR - http://www.scopus.com/inward/record.url?scp=0037446992&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0037446992&partnerID=8YFLogxK

U2 - 10.1016/S0166-218X(02)00254-8

DO - 10.1016/S0166-218X(02)00254-8

M3 - Article

AN - SCOPUS:0037446992

SN - 0166-218X

VL - 127

SP - 357

EP - 371

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 2 SPEC.

ER -

Characterizations of consistent marked graphs

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this