Abstract
The main result of the paper is Theorem 1. It concerns the sets of integral symmetric matrices with given block partition and prescribed row, column and block sums. It is shown that by interchanges preserving these sums we can pass from any two matrices, one from each set, to the other two ones falling “close” together as much as possible. One of the direct corollaries of Theorem 1 is substantiating the fact that any realization ofr-graphical integer-pair sequence can be obtained from any other one byr-switchings preserving edge degrees. This result is also of interest in connection with the problem of determinings-complete properties. In the special cases Theorem 1 includes a number of well-known results, some of which are presented.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
C. Berge,Graph and Hypergraphs, Dunod, Paris, 1970.
D. Billington, Connected subgraphs of the graph of multigraphic realizations of a degree sequences,Lect. Notes Math. 884 (1981), 125–135.
R. A. Brualdi, Matrices of zeros and ones with fixed row and column sum vectors,Lin. Al. Appl. 33 (1980), 159–231.
M. Capobianco, S. Maurer, D. McCarthy andJ. Molluzo, A collection of open problems,Ann. N.-Y. Acad. Sci. 319 (1979), 565–590.
V. Changphaisan, Conditions for sequence to ber-graphic,Discrete Math. 7 (1974), 31–39.
Zh. A. Chernyak, Characterization of self-complimentary degree sequences,Doklady Acad. Nayk BSSR 27 (1983), 497–500.
Zh. A. Chernyak, Connected realizations of edge degree sequences,Izvestia Akad. Nauk BSSR. Ser. Fiz.-Mat. Nayk 3 (1982), 43–47.
Zh. A. Chernyak andA. A. Chernyak, Edge degree sequences and their realizations,Doklady Akad. Nauk BSSR 25 (1981), 594–598.
C. J. Colbourn, Graph generation.Dept. of Computer Science, University of Waterloo, Canada, Tech. Report CS-77-37, 1977.
P. Das, Unigraphic and Unidigraphic degree sequences through uniquely realizable integer-pair sequences,Discrete Math. 45 (1983), 45–59.
R. B. Eggleton andD. A. Holton, Graphic sequences,Lect. Notes Math. 748 (1979), 1–10.
D. R. Fulkerson, A. J. Hoffman andM. H. McAndrew, Some properties of graphs with multiple edges,Canad, J. Math. 17 (1965), 166–177.
D. J. Kleitman andD. L. Wang, Algorithms for constructing graphs, digraphs with given valences and factors,Discrete Math. 6 (1973), 79–88.
S. Kundu, Thek-factor conjecture is true,Discrete Math. 6 (1973), 367–376.
A. N. Patrinos andS. L. Hakimi, Relations between graphs and integerpair sequences,Discrete Math. 15 (1976). 347–358.
H. J. Ryser, Combinatorial properties of matrices of zeros and ones,Canad. J. Math. 9 (1957), 371–377.
R. P. Anstee, The network flows approach for matrices with given row and column sums,Discrete Math. 44 (1983), 125–138.