solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看6337次
Alternating Hamiltonian cycles in $2$-edge-colored multigraphs. (arXiv:1810.04372v1 [math.CO])
来源于:arXiv
A path (cycle) in a $c$-edge-colored multigraph is alternating if no two
consecutive edges have the same color. The problem of determining the existence
of alternating Hamiltonian paths and cycles in $2$-edge-colored multigraphs is
an $\mathcal{NP}$-complete problem and it has been studied by several authors.
In Bang-Jensen and Gutin's book "Digraphs: Theory, Algorithms and
Applications", it is devoted one chapter to survey the last results on this
topic. Most results on the existence of alternating Hamiltonian paths and
cycles concern on complete and bipartite complete multigraphs and a few ones on
multigraphs with high monochromatic degrees or regular monochromatic subgraphs.
In this work, we use a different approach imposing local conditions on the
multigraphs and it is worthwhile to notice that the class of multigraphs we
deal with is much larger than, and includes, complete multigraphs, and we
provide a full characterization of this class.
Given a $2$-edge-colored multigraph $G$, 查看全文>>