z-logo
open-access-imgOpen Access
Spanning trees with a bounded number of leaves
Author(s) -
Junqing Cai,
Evelyne Flandrin,
Hao Li,
Qiang Sun
Publication year - 2017
Publication title -
opuscula mathematica
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.481
H-Index - 16
eISSN - 2300-6919
pISSN - 1232-9274
DOI - 10.7494/opmath.2017.37.4.501
Subject(s) - mathematics , bounded function , spanning tree , combinatorics , mathematical analysis
In 1998, H. Broersma and H. Tuinstra proved that: Given a connected graph \(G\) with \(n\geq 3\) vertices, if \(d(u)+d(v)\geq n-k+1\) for all non-adjacent vertices \(u\) and \(v\) of \(G\) (\(k\geq 1\)), then \(G\) has a spanning tree with at most \(k\) leaves. In this paper, we generalize this result by using implicit degree sum condition of \(t\) (\(2\leq t\leq k\)) independent vertices and we prove what follows: Let \(G\) be a connected graph on \(n\geq 3\) vertices and \(k\geq 2\) be an integer. If the implicit degree sum of any \(t\) independent vertices is at least \(\frac{t(n-k)}{2}+1\) for (\(k\geq t\geq 2\)), then \(G\) has a spanning tree with at most \(k\) leaves

The content you want is available to Zendy users.

Already have an account? Click here to sign in.
Having issues? You can contact us here
Accelerating Research

Address

John Eccles House
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom