The degree sequences of a graph with restrictions

Rikio Ichishima, Francesc A. Muntaner-Batle, Miquel Rius-Font, Yukio Takahashi


Two finite sequences s1 and s2 of nonnegative integers are called bigraphical if there exists a bipartite graph G with partite sets V1 and V2 such that s1 and s2 are the degrees in G of the vertices in V1 and V2, respectively. In this paper, we introduce the concept of 1-graphical sequences and present a necessary and sufficient condition for a sequence to be 1-graphical in terms of bigraphical sequences.

Full Text:




G. Chartrand and L. Lesniak, Graphs & Digraphs 3th ed. CRC Press (1996).

D. Gale, A theorem on flows in networks, Pacific J. Math. 7 (2), (1957), 1073--1082.

S. Hakimi, On the realizability of a set of integers as degrees of the vertices of a graph, J. SIAM Appl. Math. 10 (1962), 496-–506.

V. Havel, A remark on the existence of finite graphs (Czech), Casopis Pest. Math. 80 (1955), 477--480.

S. C. Lopez and F. A Muntaner-Batle, Mirror bipartite graphs, preprint, 2013. Available at ´

H. J. Ryser, Combinatorial properties of matrices of zeros and ones, Can. J. Math. 9 (1957), 371--377.

O. Veblen, An application of modular equations in analysis situs, Math. Ann. 14 (1912–1913), 86--94.


  • There are currently no refbacks.

ISSN: 2541-2205

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View IJC Stats