Spanning \(k\)-trees of bipartite graphs
type: Item
instance of: scholarly article
title: Spanning \(k\)-trees of bipartite graphs
zbMATH Open document ID: 1305.05046
author: Mikio Kano
author: Kenta Ozeki
author: Kazuhiro Suzuki
author: Masao Tsugaki
author: Tomoki Yamashita
published in: The Electronic Journal of Combinatorics
publication date: 2015-01-22T00:00:00Z
full work available at URL: v22i1p13
review text: Summary: A tree is called a \(k\)-tree if its maximum degree is at most \(k\). We prove the following theorem. Let \(k \geq 2\) be an integer, and \(G\) be a connected bipartite graph with bipartition \((A,B)\) such that \(|A| \leq |B| \leq (k-1)|A|+1\). If \(\sigma_k(G) \geq |B|\), then \(G\) has a spanning \(k\)-tree, where \(\sigma_k(G)\) denotes the minimum degree sum of \(k\) independent vertices of \(G\). Moreover, the condition on \(\sigma_k(G)\) is sharp. It was shown by \textit{S. Win} [Abh. Math. Semin. Univ. Hamb. 43, 263--267 (1975; Zbl 0309.05122)] that if a connected graph \(H\) satisfies \(\sigma_k(H) \geq |H|-1\), then \(H\) has a spanning \(k\)-tree. Thus our theorem shows that the condition becomes much weaker if the graph is bipartite.
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 6389252
zbMATH Keywords: spanning tree
zbMATH Keywords: spanning \(k\)-tree
zbMATH Keywords: bipartite graph
MaRDI profile type: Publication
cites work: Factors and factorizations of graphs. Proof techniques in factor theory
cites work: Spanning trees of bounded degree
cites work: On a \(k\)-tree containing specified leaves in a graph
cites work: On Hamiltonian bipartite graphs
cites work: Spanning trees with bounded degrees
cites work: Spanning trees: A survey
cites work: Existenz von Gerüsten mit vorgeschriebenem Maximalgrad in Graphen
description: scientific article; zbMATH DE number 6389252