Is there a formal name of the "Hamiltonian property" of a node-weighted graph？

Question

Given a node-weighted graph $G = (V,E)$ with weight $w \colon V \to \mathbb{N}^{*}$.

The "Hamiltonian property" of $G$: There exists a cycle (path) $c$ that traverses the vertex $v_{i}$ exactly $w(v_{i})$ times ($i = 1,2, \ldots , |V|$).

Note that it is allowed that $c$ traverses an edge more than once.

I hope there is a formal name of it so that I can differentiate between this "Hamiltonian property" and the Hamiltonian property of a simple graph.

Answer 1

The best way I know of to talk about this problem in existing terminology is to talk about blow-up graphs.

Given a graph $H$ and a function $k : V(H) \to \mathbb Z^+$ (here, $k$ is the same as your vertex weights $w$), the $k$-blow-up of $H$, denoted $H^{(k)}$, is the graph where:

• For every vertex $v \in V(H)$, the blow-up has $k(v)$ vertices $(v,1), (v,2), \dots, (v, k(v))$.
• Vertices $(v,i)$ and $(w,j)$ in $H^{(k)}$ are adjacent if and only if $v$ and $w$ are adjacent in $H$.

Your question about the "Hamiltonian" property of a vertex-weighted graph is equivalent to asking if the blow-up graph is Hamiltonian.

I don't know of existing terminology for this question, but if you're writing anything formal about it, I suggest reminding readers of the definition of a blow-up graph, then defining something like

Given a vertex-weighted graph $H$ with weight function $k$, we say that $H$ is blow-up Hamiltonian if the $k$-blow-up of $H$ has a Hamiltonian cycle.

or

We say that a $k$-Hamiltonian cycle (path) in a graph $H$, where $k$ is a function $V(H) \to \mathbb Z^*$, is a Hamiltonian cycle (path) in the $k$-blow-up of $H$.

Answer 2

I don't know whether a specific name already exists, but weighted Hamilton property might be a natural candidate.