Some Remarks on Graphical Sequences for Graphs and Bipartite Graphs

arXiv1302.3657MaRDI QIDQ6239652FDOQ6239652

Authors: Grant Cairns, Stacey Mendan 

Publication date: 14 February 2013

Abstract: For finite sequence $underbaremd$ of positive integers, we consider graphs that have $underbaremd$ as their list of vertex degrees, and bipartite graphs for which each part has $underbaremd$ as its list of vertex degrees. In particular, we make a connection between a result for bipartite graphs by Alon, Ben-Shimon and Krivelevich and a result of Zverovich and Zverovich for graphs, and we give an improvement of a result of Zverovich and Zverovich. We show that the bipartite graphs with vertex degree sequences $(underbaremd,underbaremd,)$ are in one to one correspondence with graphs with loops with reduced degree sequence $underbaremd$, where the reduced degree of a vertex is defined to be the number of edges incident to the vertex, with loops counted only once. We also give two ErdH{o}s--Gallai type theorems for graphs with loops.

Mathematics Subject Classification ID

Vertex degrees (05C07)

This page was built for publication: Some Remarks on Graphical Sequences for Graphs and Bipartite Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6239652)