Two new characterizations of consistent marked graph
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
A consistent marked graph is a graph in which every vertex is signed + or −, and where every cycle has an even number of negative vertices. Theorem. For a consistent marked graph G, the following statements are equivalent 1) G is consistent. 2) There exists a partition {E_1,E-2} of the edge set of each cycle C in G such that every negative vertex on C, appears as an end vertex of an edge in each of the sets E_1 and E_2, and no positive vertex on C has this property. 3) The edge set of each cycle C in G can be partitioned into two sets {E_1,E_2} such that any two adjacent edges in C belong to different sets in {E_1,E_2} if, and only if, they have a common negative vertex.
Abstract
A consistent marked graph is a graph in which every vertex is signed + or −, and where every cycle has an even number of negative vertices. Theorem. For a consistent marked graph G, the following statements are equivalent 1) G is consistent. 2) There exists a partition {E_1,E-2} of the edge set of each cycle C in G such that every negative vertex on C, appears as an end vertex of an edge in each of the sets E_1 and E_2, and no positive vertex on C has this property. 3) The edge set of each cycle C in G can be partitioned into two sets {E_1,E_2} such that any two adjacent edges in C belong to different sets in {E_1,E_2} if, and only if, they have a common negative vertex.
참고문헌 (4)
- B. D. Acharya, "A characterization of consistent marked graphs", Nat. Acad. Sci. lett, 6, pp.431~440 (1983)
- F. Harary, "On the notion of balance of a signed graph", Michigan Math. J, 2, pp.143~146 (1953)
- C. Hoede, "A Characterization of consistent marked graphs", J. Graph Thoery, 16, pp.17~23 (1992)
- F. S. Roberts, "Characterizations of consistent marked graphs", Discrete Appl.Math, 127, pp.357~371 (2003)