Bipartite embedding of (p, q)-trees

Abstract

A bipartite graph $G=(L,R;E)$ where $V(G)=L\cup R$, $|L|=p$, $|R|=q$ is called a $(p,q)$-tree if $|E(G)|=p+q−1$ and $G$ has no cycles. A bipartite graph $G=(L,R;E)$ is a subgraph of a bipartite graph $H=(L',R';E')$ if $L\subseteq L'$, $R\subseteq R'$ and $E\subseteq E'$. In this paper we present sufficient degree conditions for a bipartite graph to contain a $(p,q)$-tree.