On the SPANNING \(k\)-TREE problem
type: Item
instance of: scholarly article
title: On the SPANNING \(k\)-TREE problem
zbMATH Open document ID: 0788.68107
DOI: 10.1016/0166-218X(93)90228-G
author: Leizhen Cai
author: Frédéric Maffray
published in: Discrete Applied Mathematics
publication date: 1993-11-30T00:00:00Z
review text: A \(k\)-tree \(T\) is defined recursively as being either a clique of size \(k\) or having a vertex \(x\) whose neighbourhood is a clique of size \(k\) and such that \(T-x\) is a \(k\)-tree. (Note that \(k\)-trees are not trees, if \(k>1\).) The following SPANNING \(k\)-TREE problem is known to be NP-complete: given a graph \(G\), does \(G\) possess a subgraph which is a \(k\)-tree and contains every vertex of \(G\)? The main result of the paper: the SPANNING \(k\)-TREE problem remains NP-complete for all \(k \geq 2\) even when restricted to any of the following classes of graphs: split graphs, graphs with maximum degree at most \(3k+2\), planar graphs (for \(k=2)\).
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 428109
zbMATH Keywords: spanning tree
zbMATH Keywords: \(k\)-tree
zbMATH Keywords: NP-complete
reviewed by: S. V. Duzhin
MaRDI profile type: Publication
cites work: Complexity of Finding Embeddings in a k-Tree
cites work: Properties and characterizations of k ‐trees
cites work: Q4099676
cites work: Q4138187
cites work: A Dynamic Programming Approach to the Dominating Set Problem on k-Trees
cites work: On rigid circuit graphs
cites work: Networks immune to isolated failures
cites work: Q3337498
cites work: Q3291037
cites work: A Characterization of Comparability Graphs and of Interval Graphs
cites work: Q3328583
cites work: Q4193514
cites work: Split Graphs Having Dilworth Number Two
cites work: Planar Formulae and Their Uses
cites work: On simple characterizations of k-trees
cites work: Algorithmic Aspects of Vertex Elimination on Graphs
cites work: Q3707420
cites work: Steiner trees, partial 2–trees, and minimum IFI networks
full work available at URL: 0166-218x(93)90228-g
OpenAlex ID: W2062226917
Recommended article: The \((K, k)\)-capacitated spanning tree problem
Recommended article: The (K,k)-Capacitated Spanning Tree Problem
Recommended article: Q3088444
Recommended article: Q3004302
Recommended article: Spanning \(k\)-trees of \(n\)-connected graphs
Recommended article: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
Recommended article: Complexities of some interesting problems on spanning trees
Recommended article: Q4871148
Recommended article: Approximating the Spanning k-Tree Forest Problem
Recommended article: APPROXIMATING THE SPANNING k-TREE FOREST PROBLEM
description: scientific article; zbMATH DE number 428109