Opuscula Math. 26, no. 1 (2006), 119-125

Opuscula Mathematica

# Bipartite embedding of (p,q)-trees

Beata Orchel

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.

Keywords: bipartite graph, tree, embedding graph.

Mathematics Subject Classification: 05C35.

Full text (pdf)

• Beata Orchel
• AGH University of Science and Technology, Faculty of Applied Mathematics, al. Mickiewicza 30, 30-059 Kraków, Poland