Spanning trees with many leaves and average distance

MaRDI QIDQ1010741zbMATH OpenFDO

Authors Ermelinda DeLaViña, Bill Waller

Publication date 7 April 2009

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

Full work available at URL https://eudml.org/doc/117225, http://www.emis.de/journals/EJC/Volume_15/Abstracts/v15i1r33.html

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

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35)

Review text

Summary: We prove several new lower bounds on the maximum number of leaves of a spanning tree of a graph related to its order, independence number, local independence number, and the maximum order of a bipartite subgraph. These new lower bounds were conjectured by the program Graffiti.pc, a variant of the program Graffiti. We use two of these results to give two partial resolutions of conjecture 747 of Graffiti (circa 1992), which states that the average distance of a graph is not more than half the maximum order of an induced bipartite subgraph. If correct, this conjecture would generalize conjecture number 2 of Graffiti, which states that the average distance is not more than the independence number. Conjecture number 2 was first proved by F. Chung. In particular, we show that the average distance is less than half the maximum order of a bipartite subgraph, plus one-half; we also show that if the local independence number is at least five, then the average distance is less than half the maximum order of a bipartite subgraph. In conclusion, we give some open problems related to average distance or the maximum number of leaves of a spanning tree.

Recommendations

• Average distance, independence number, and spanning trees
• Average distance and maximum induced forest
• scientific article; zbMATH DE number 5037210
• scientific article; zbMATH DE number 508964
• Bounds of the number of leaves of spanning trees

Cited in

(32)

• Leaf number and Hamiltonian \(C_4\)-free graphs
• Graphs with forbidden subgraphs and leaf number
• Spanning paths in graphs
• On eccentric distance sum and degree distance of graphs
• Wiener index of graphs with radius two
• Graphs with a given diameter that maximise the Wiener index
• Further results on the total monochromatic connectivity of graphs
• Further results on the Merrifield-Simmons index
• Comparative results and bounds for the eccentric-adjacency index
• An asymptotic resolution of a problem of Plesník
• Spanning trees with leaf distance at least \(d\)
• On maximum Wiener index of trees and graphs with given radius
• On spanning cycles, paths and trees
• Minimum degree, leaf number and traceability.
• Connected domination
• Spanning trees with leaf distance at least four
• Average distance and maximum induced forest
• scientific article; zbMATH DE number 1743972 (Why is no real title available?)
• On the total distance and diameter of graphs
• scientific article; zbMATH DE number 2170329 (Why is no real title available?)
• Bounds on the leaf number in graphs of girth 4 or 5
• Relationships between some distance-based topological indices
• On minimum degree, leaf number, traceability and Hamiltonicity in graphs
• Lower bounds on the leaf number in graphs with forbidden subgraphs
• Average distance, independence number, and spanning trees
• Spanning trees with many leaves
• The extremal average distance of cubic graphs
• Average distance and connected domination
• Average distance in weighted graphs
• Selected topics on Wiener index
• The average solution of a TSP instance in a graph
• Average distance and generalised packing in graphs

This page was built for publication: Spanning trees with many leaves and average distance

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