Bipartite embedding of (p, q)-trees

• Autorzy: Orchel B.
• Języki publikacji: EN

Abstrakty

EN

A bipartite graph G = (L, R; E) where V(G) = L ∪ 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 ⊆ L', R ⊆ R' and E ⊆ E'. In this paper we present sufficient degree conditions for a bipartite graph to contain a (p, q)-tree.

Słowa kluczowe

EN

bipartite graph; tree; embedding graph

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2006
• Tom: Vol. 26, no. 1
• Strony: 119--125
• Opis fizyczny: Bibliogr. 6 poz.

Twórcy

autor

Orchel B.

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

Bibliografia

• [1] Bollobas B., Extremal Graph Theory, in: Handbook of Combinatorics R.I. Graham, M. Groschel, L. Lovasz, (ed.), The MIT Press, Cambridge, Massachusetts. 1995.
• [2] Brandt S., Subtrees and subforests of graphs, J. Combin. Theory Ser. B. 61 (1994), 63-70.
• [3] Catlin Paul A., Subgraphs of graphs, 1, Discrete Mathematics 10 (1974), 225-233
• [4] Chvatal V., Tree - complete graph Ramsey numbers, J. Graph Theory 1 (1977), 93.
• [5] Erdos P., Extremal problems in graph theory, in: Theory of Graphs and its applications M. Fiedler (ed.), Academic Press, 1964, 29-36.
• [6] Rado R., A theorem on general measure functions, Proc. London Math. Soc. 44 (1938) (2).