Hostname: page-component-cd9895bd7-p9bg8 Total loading time: 0 Render date: 2024-12-26T16:38:28.599Z Has data issue: false hasContentIssue false
  • English
  • Français

A SUFFICIENT CONDITION FOR A PAIR OF SEQUENCES TO BE BIPARTITE GRAPHIC

Part of: Graph theory

Published online by Cambridge University Press:  25 April 2016

GRANT CAIRNS ,
STACEY MENDAN  and
YURI NIKOLAYEVSKY
GRANT CAIRNS
Affiliation:
Department of Mathematics and Statistics, La Trobe University, Melbourne 3086, Australia email [email protected]
STACEY MENDAN
Affiliation:
Department of Mathematics and Statistics, La Trobe University, Melbourne 3086, Australia email [email protected]
YURI NIKOLAYEVSKY*
Affiliation:
Department of Mathematics and Statistics, La Trobe University, Melbourne 3086, Australia email [email protected]
*
✉[email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We present a sufficient condition for a pair of finite integer sequences to be degree sequences of a bipartite graph, based only on the lengths of the sequences and their largest and smallest elements.

Keywords

bipartite graphdegree sequence

MSC classification

Primary: 05C07: Vertex degrees
Type
Research Article
Information
Bulletin of the Australian Mathematical Society , Volume 94 , Issue 2 , October 2016 , pp. 195 - 200
Copyright
© 2016 Australian Mathematical Publishing Association Inc. 

References

Alon, N., Ben-Shimon, S. and Krivelevich, M., ‘A note on regular Ramsey graphs’, J. Graph Theory 64(3) (2010), 244–249.Google Scholar
Barrus, M. D., Hartke, S. G., Jao, K. F. and West, D. B., ‘Length thresholds for graphic lists given fixed largest and smallest entries and bounded gaps’, Discrete Math. 312(9) (2012), 1494–1501.Google Scholar
Cairns, G. and Mendan, S., ‘Symmetric bipartite graphs and graphs with loops’, Discrete Math. Theor. Comput. Sci. 17(1) (2015), 97–102.Google Scholar
Cairns, G. and Mendan, S., ‘An improvement of a result of Zverovich–Zverovich’, Ars Math. Contemp. 10(1) (2016), 79–83.Google Scholar
Cairns, G., Mendan, S. and Nikolayevsky, Y., ‘A sharp refinement of a result of Alon, Ben-Shimon and Krivelevich on bipartite graph vertex sequences’, Australas. J. Combin. 60 (2014), 217–226.Google Scholar
Cairns, G., Mendan, S. and Nikolayevsky, Y., ‘A sharp refinement of a result of Zverovich–Zverovich’, Discrete Math. 338(7) (2015), 1085–1089.Google Scholar
Gale, D., ‘A theorem on flows in networks’, Pacific J. Math. 7 (1957), 1073–1082.Google Scholar
Miller, J. W., ‘Reduced criteria for degree sequences’, Discrete Math. 313 (2013), 550–562.Google Scholar
Ryser, H. J., ‘Combinatorial properties of matrices of zeros and ones’, Canad. J. Math. 9 (1957), 371–377.Google Scholar
Zverovich, I. È. and Zverovich, V. È., ‘Contributions to the theory of graphic sequences’, Discrete Math. 105(1–3) (1992), 293–303.Google Scholar