A Note on Construction of Dual-Hamiltonian Graphs

MaRDI QIDQ6294938zbMATH OpenFDO

Authors João Paulo Costalonga

Publication date 6 December 2017

Abstract: A connected simple graph is said dual-hamiltonian if its vertex set has a $2$-coloring such that each color class induces a tree. We call such a coloring a hamiltonian coloring. We prove that if $G$ is a graph with a certain type of hamiltonian coloring and $T$ is a tree, then $GimesT$ is also dual-hamiltonian having the same certain type of hamiltonian coloring. This result is used to constructed a class of dual-hamiltonian graphs, which includes the hypercubes and other multidimensional grids.

This page was built for publication: A Note on Construction of Dual-Hamiltonian Graphs

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