Paper Info
Title
Depth first search in claw-free graphs.
Abstract
Optimization problems concerning the vertex degrees of spanning trees of connected graphs play an extremely important role in network design. Minimizing the number of leaves of the spanning trees is NP-hard, since it is a generalization of the problem of finding a hamiltonian path of the graph. Moreover, Lu and Ravi (The power of local optimization: approximation algorithms for maximum-leaf spanning tree (DRAFT), CS-96-05, Department of Computer Science, Brown University, Providence, 1996) showed that this problem does not even have a constant factor approximation, unless \(\hbox {P}=\hbox {NP}\), thus properties that guarantee the existence of a spanning tree with a small number of leaves are of special importance. In this paper we are dealing with finding spanning trees with few leaves in claw-free graphs. We prove that all claw-free graphs have a DFS-tree, such that the leaves different from the root have no common neighbour, generalizing a theorem of Kano et al. (Ars Combin 103:137–154, 2012). The result also implies a strengthening of a result of Ainouche et al. (Ars Combin 29C:110–121, 1990).
Year
DOI
Venue
2018
10.1007/s11590-017-1211-0
Optimization Letters
Keywords
Field
DocType
Claw-free graph, Spanning tree, Depth first search
Approximation algorithm,Discrete mathematics,Combinatorics,Claw-free graph,Vertex (geometry),Hamiltonian path,Breadth-first search,Spanning tree,Local search (optimization),Optimization problem,Mathematics
Journal
Volume
Issue
ISSN
12
2
1862-4472
Citations 
PageRank 
References 
0
0.34
7
Authors
1
Name
Order
Citations
PageRank
Gábor Wiener16410.65