Small \(k\)-pyramids and the complexity of determining \(k\)

DOI10.1016/j.jda.2014.11.003zbMath1320.05130OpenAlexW2087090890MaRDI QIDQ2253900

Boris Schauerte, Carol T. Zamfirescu

Publication date: 13 February 2015

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2014.11.003

zbMATH Keywords

prismpyramidHamiltonianHalin graph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Eulerian and Hamiltonian graphs (05C45)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On cubic planar hypohamiltonian and hypotraceable graphs
• On approximating the minimum independent dominating set
• Clustering and domination in perfect graphs
• The smallest non-Hamiltonian 3-connected cubic planar graphs have 38 vertices
• Independent domination in chordal graphs
• On the algorithmic complexity of twelve covering and independence parameters of graphs
• A recurrence template for several parameters in series-parallel graphs
• The algorithmic use of hypertree structure and maximum neighbourhood orderings
• Hamiltonian properties of generalized pyramids
• Domination on Cocomparability Graphs
• Hamiltonian Properties of Generalized Halin Graphs
• On the Cutting Edge: Simplified O(n) Planarity by Edge Addition
• Three small cubic graphs with interesting hamiltonian properties
• Edge Dominating Sets in Graphs
• The Planar Hamiltonian Circuit Problem is NP-Complete
• Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
• Independent sets in asteroidal triple-free graphs
• Nonhamiltonian 3-Connected Cubic Planar Graphs
• Reducibility among Combinatorial Problems
• Exact Algorithms for Finding the Minimum Independent Dominating Set in Graphs