Characterizations of consistent marked graphs

DOI10.1016/S0166-218X(02)00254-8MaRDI QIDQ1874545zbMATH OpenOpenAlexFDO

Authors Fred Roberts, Shaoji Xu

Publication date 25 May 2003

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0166-218x(02)00254-8

Mathematics Subject Classification ID

Signed and weighted graphs (05C22) Structural characterization of families of graphs (05C75)

Review text

A marked graph is a graph in which to each vertex a sign \(+\) or \(-\) is assigned. A marked graph is called consistent, if on each of its cycles there is an even number of \(-\) signs. Some theorems are proved. Some of them characterize consistent graphs. Two algorithms are described; the first of them recognizes whether a given 2-connected marked graph is consistent. The introduction of the above-mentioned concepts is motivated by their application in social sciences.

Recommendations

• A characterization of consistent marked graphs
• Characterization of a signed graph whose signed line graph is \(S\)-consistent
• Some further properties of consistent marked graphs
• On the problem of consistent marking of a graph
• A characterization of consistent marked graphs

Cites work

• A characterization of consistent marked graphs
• A characterization of consistent marked graphs
• A simple algorithm to detect balance in signed graphs
• Consistency in marked digraphs
• Consistent graphs with signed points
• Counting balanced signed graphs using marked graphs
• Enumeration of graphs with signed points and lines
• scientific article; zbMATH DE number 4014777 (Why is no real title available?)
• scientific article; zbMATH DE number 4156493 (Why is no real title available?)
• scientific article; zbMATH DE number 3688740 (Why is no real title available?)
• scientific article; zbMATH DE number 3558962 (Why is no real title available?)
• scientific article; zbMATH DE number 3793772 (Why is no real title available?)
• scientific article; zbMATH DE number 4197819 (Why is no real title available?)
• Is every cycle basis fundamental?
• On the problem of consistent marking of a graph
• Some further properties of consistent marked graphs
• Structural properties and recognition of restricted and strongly unimodular matrices

Cited in

(15)

• On the problem of consistent marking of a graph
• A remark on eigen values of signed graph
• Characterization of line-consistent signed graphs
• Enumeration of balanced finite group valued functions on directed graphs
• scientific article; zbMATH DE number 4014777 (Why is no real title available?)
• scientific article; zbMATH DE number 5995086 (Why is no real title available?)
• Submarking reachability of marked graphs
• Groups of balanced labelings on graphs
• Balanced group-labeled graphs
• ALGEBRAIC STRUCTURES RELATED TO BALANCED FUNCTIONS ON GRAPHS: RESULTS AND OPEN PROBLEMS
• A characterization of consistent marked graphs
• On balance and consistency preserving 2-path signed graphs
• Characterization of signed graphs whose iterated signed line graphs are balanced or S-consistent
• A characterization of consistent marked graphs
• Some further properties of consistent marked graphs

This page was built for publication: Characterizations of consistent marked graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1874545)