Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
signed graphs
signed graphs
Summary:
The set $D$ of distinct signed degrees of the vertices in a signed graph $G$ is called its signed degree set. In this paper, we prove that every non-empty set of positive (negative) integers is the signed degree set of some connected signed graph and determine the smallest possible order for such a signed graph. We also prove that every non-empty set of integers is the signed degree set of some connected signed graph.
References:
[1] G. Chartrand, H. Gavlas, F. Harary and M. Schultz: On signed degrees in signed graphs. Czech. Math. J. 44 (1994), 677–690. MR 1295143
[2] S. L. Hakimi: On the realizability of a set of integers as degrees of the vertices of a graph. SIAM J. Appl. Math. 10 (1962), 496–506. DOI 10.1137/0110037 | MR 0148049
[3] F. Harary: On the notion of balance in a signed graph. Michigan Math. J. 2 (1953), 143–146. DOI 10.1307/mmj/1028989917 | MR 0067468
[4] S. F. Kapoor, A. O. Polimeni and C. E. Wall: Degree sets for graphs. Fund. Math. 65 (1977), 189–194. MR 0480200
[5] J. H. Yan, K. W. Lih, D. Kuo and G. J. Chang: Signed degree sequences of signed graphs. J. Graph Theory 26 (1997), 111–117. DOI 10.1002/(SICI)1097-0118(199710)26:2<111::AID-JGT6>3.0.CO;2-V | MR 1469358
Search
Partner of
