Graphs whose vertices are forests with bounded degree: traceability

MaRDI QIDQ2839646zbMATH OpenFDO

Authors Edgar G. DuCasse, Louis V. Quintas, Marcelo O. Zimmler

Publication date 12 July 2013

Published in Bulletin of the Institute of Combinatorics and its Applications (Search for Journal in Brave)

zbMATH Keywords

\(f\)-graphdegreeforesttraceability

Mathematics Subject Classification ID

Vertex degrees (05C07) Coloring of graphs and hypergraphs (05C15)

Review text

A graph is said to be an \(f\)-graph if it has no vertex of degree greater than \(f\). The paper studies the Hamilton path properties of graphs whose vertices are the set of unlabeled \(f\)-forest and whose edges are such that there is an edge between vertices \(v\) and \(u\) if and only if, up to isomorphism, \(v\) and \(u\) differ by exactly on edge. In other words, if \(v\) is adjacent to \(u\), then either \(v\) is a one-edge deleted sub-forest of \(u\) or \(v\) is a one-edge extended super \(f\)-forest of \(u\). A graph is called traceable if it contains a Hamilton path. The paper studies the traceability of such graphs.

Recommendations

• Graphs whose vertices are forests with bounded degree: planarity
• scientific article; zbMATH DE number 5919777
• scientific article; zbMATH DE number 1416060
• The existence of \(f\)-forests and \(f\)-trees in graphs
• Hamilton paths in graphs whose vertices are graphs

Cited in

(4)

• Forbidding multiple copies of forestable graphs
• Graphs whose vertices are forests with bounded degree: planarity
• scientific article; zbMATH DE number 5919777 (Why is no real title available?)
• scientific article; zbMATH DE number 1416060 (Why is no real title available?)

This page was built for publication: Graphs whose vertices are forests with bounded degree: traceability

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