On Bigraphic Sequences And Potentially P-Graphic Sequences

Let S=?a₁,...,a_m;b1,...,bn?be a pair of two nonincreasing sequences of positive integers,that is,a₁,...,a_m and b1,...,bn are two nonincreasing sequences of positive integers.The pair S =?a₁,...,a_m;b1,...,bn?is said to be a bigraphic pair if there is a simple bipartite graph G =?X?Y,E?such that a₁,...,a_m and b1,...,bn are the degrees of the vertices in X and Y,respectively.In this paper,we give a simple sufficient condition for a pair S=?a₁,...,a_m;b1,...,bn?to be a bigraphic pair.The condition depends only on the lengths of two sequences of the pair and theirs largest and smallest elements.This result extends a result due to Alon,Ben-Shimon and Krivelevich?J.Graph Theory,64?3??2010?244-249?.A non-increasing sequence ?=?d₁,...,d_n?of nonnegative integers is said to be graphic if it is the degree sequence of a simple graph G on n vertices.We say that G is a realization of 7r.Let G be a connected graph.We say that |E|-|V|+1 is the cyclomatic number of G,denoted by c?G?.If c?G?=1,2 and 3,then G is said to be a unicyclic graph,bicyclic graph and tricyclic graph,respectively.We also give a sufficient and necessary condition for?d₁,d2,...,d_n?to be the degree sequence of the graph with cyclomatic number k.Let ? =?d₁,...,d_n?be graphic sequence,and let G be a realization of ?.If G contains a 3-regular graph of order r as its subgraph,we say that ? is potentially Pr3-graphic.In this paper,we also explore the condition that ? is potentially Pr3-graphic.