Opuscula Math. 26, no. 1 (2006), 119-125
Opuscula Mathematica
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.
Keywords: bipartite graph, tree, embedding graph.
Mathematics Subject Classification: 05C35.
- Beata Orchel
- AGH University of Science and Technology, Faculty of Applied Mathematics, al. Mickiewicza 30, 30-059 Kraków, Poland
- Received: 2005-04-28.
