Spanning k-trees of bipartite graphs

MaRDI QIDQ490315zbMATH OpenFDO

Authors Mikio Kano, Kenta Ozeki, Kazuhiro Suzuki, Masao Tsugaki, Tomoki Yamashita

Publication date 22 January 2015

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p13

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

bipartite graphspanning \(k\)-treespanning tree

Mathematics Subject Classification ID

Trees (05C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

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.

Recommendations

• Spanning \(k\)-ended trees of bipartite graphs
• On a spanning \(k\)-tree in which specified vertices have degree less than \(k\)
• On a spanning \(K\)-tree containing specified vertices in a graph
• A forbidden pair for connected graphs to have spanning k‐trees
• Spanning \(k\)-trees of \(n\)-connected graphs

Cites work

• Existenz von Gerüsten mit vorgeschriebenem Maximalgrad in Graphen
• Factors and factorizations of graphs. Proof techniques in factor theory
• On a k-tree containing specified leaves in a graph
• On Hamiltonian bipartite graphs
• Spanning trees of bounded degree
• Spanning trees with bounded degrees
• Spanning trees: A survey

Cited in

(17)

• Spanning trees in multipartite geometric graphs
• Rainbow and properly colored spanning trees in edge-colored bipartite graphs
• Degree conditions for completely independent spanning trees of bipartite graphs
• Maximum properly colored trees in edge-colored graphs
• \(k\)-ary spanning trees contained in tournaments
• On a spanning \(K\)-tree containing specified vertices in a graph
• A note on a spanning \((\alpha ,\beta )\)-ended tree in a bipartite graph
• Spanning \(k\)-ended trees of bipartite graphs
• The Q-spectrum and spanning trees of tensor products of bipartite graphs
• Spanning bipartite quadrangulations of even triangulations
• Counting degree sequences of spanning trees in bipartite graphs: A graph‐theoretic proof
• Bipartite embedding of \((p,q)\)-trees
• scientific article; zbMATH DE number 5054175 (Why is no real title available?)
• The spanning k-trees, perfect matchings and spectral radius of graphs
• Spanning trees of bipartite graphs with a bounded number of leaves and branch vertices
• Sufficient conditions for k-factor-critical graphs and spanning k-trees of graphs
• Tree spanners for bipartite graphs and probe interval graphs

This page was built for publication: Spanning \(k\)-trees of bipartite graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q490315)