Spanning paths in graphs

The Conjecture, Graffiti.pc 190, of the computer program Graffiti.pc, instructed by DeLaviña, state that every simple connected graph G with minimum degree δ and leaf number L(G) such that δ≥12(L(G)+1), is traceable. Here, we prove a sufficient condition for a graph to be traceable based on minimum...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2019-02, Vol.255, p.278-282
Main Authors: Mafuta, Phillip, Mukwembi, Simon, Munyira, Sheunesu
Format: Article
Language:English
Subjects:
Graffiti
Graphs
Leaf number
Minimum degree
Personal computers
Traceable graphs
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The Conjecture, Graffiti.pc 190, of the computer program Graffiti.pc, instructed by DeLaviña, state that every simple connected graph G with minimum degree δ and leaf number L(G) such that δ≥12(L(G)+1), is traceable. Here, we prove a sufficient condition for a graph to be traceable based on minimum degree and leaf number, by settling completely, the Conjecture Graffiti.pc 190. We construct infinite graphs to show that our results are best in a sense. All graphs considered are simple. That is, they neither have loops nor multiple edges.
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2018.08.001