I have tried to install it to my computer. It fails with:

[DZ] attempt to add META.yml multiple times; added by: filename set by
+ GatherDir (Dist::Zilla::Plugin::GatherDir line 235); encoded_content
+ added by @Basic/GatherDir (Dist::Zilla::Plugin::GatherDir line 236);
+ text from coderef added by @Basic/MetaYAML (Dist::Zilla::Plugin::Met
+aYAML line 78)
[DZ] attempt to add LICENSE multiple times; added by: filename set by 
+GatherDir (Dist::Zilla::Plugin::GatherDir line 235); encoded_content 
+added by @Basic/GatherDir (Dist::Zilla::Plugin::GatherDir line 236); 
+content added by @Basic/License (Dist::Zilla::Plugin::License line 45
+)
[DZ] attempt to add README multiple times; added by: filename set by G
+atherDir (Dist::Zilla::Plugin::GatherDir line 235); encoded_content a
+dded by @Basic/GatherDir (Dist::Zilla::Plugin::GatherDir line 236); c
+ontent added by @Basic/Readme (Dist::Zilla::Plugaborting; duplicate f
+iles would be produced at /usr/local/share/perl5/5.32/Dist/Zilla/App/
+Command/install.pm line 55.
in::Readme line 52); content set by Readme (Dist::Zilla::Plugin::Readm
+e line 69)
[DZ] attempt to add Makefile.PL multiple times; added by: filename set
+ by GatherDir (Dist::Zilla::Plugin::GatherDir line 235); encoded_cont
+ent added by @Basic/GatherDir (Dist::Zilla::Plugin::GatherDir line 23
+6); content set by MakeMaker (Dist::Zilla::Plugin::MakeMaker line 337
+); content added by @Basic/MakeMaker (Dist::Zilla::Plugin::MakeMaker 
+line 152)
[DZ] attempt to add MANIFEST multiple times; added by: filename set by
+ GatherDir (Dist::Zilla::Plugin::GatherDir line 235); encoded_content
+ added by @Basic/GatherDir (Dist::Zilla::Plugin::GatherDir line 236);
+ bytes from coderef added by @Basic/Manifest (Dist::Zilla::Plugin::Ma
+nifest line 63)
-> FAIL Installing . failed. See xxx/.cpanm/work/1640862473.22542/buil
+d.log for details. Retry with --force to force install it.
[download]

Could the multiple times; be the culprit?

Anyway, if you want to switch to ExtUtils::MakeMaker, then here is a basic Makefile.PL:

use 5.006;
use strict;
use warnings;
use ExtUtils::MakeMaker;

WriteMakefile(
#EDIT: only for testing
#INSTALL_BASE => 'xxx',
    NAME             => 'Graph::Undirected::Hamiltonicity',
    AUTHOR           => q{XXX <XXX@cpan.org>},
    VERSION_FROM     => 'lib/Graph/Undirected/Hamiltonicity.pm',
    ABSTRACT_FROM    => 'lib/Graph/Undirected/Hamiltonicity.pod',
    LICENSE          => 'artistic_2',
    PL_FILES         => {},
    MIN_PERL_VERSION => '5.006',
    CONFIGURE_REQUIRES => {
        'ExtUtils::MakeMaker' => '0',
    },
    BUILD_REQUIRES => {
        'Test::More' => '0',
    },
    PREREQ_PM => {
        # add here dependencies
        #'ABC'              => '1.6',
        #'Foo::Bar::Module' => '5.0401',
    },
    # it adds your scripts too in bin/
    EXE_FILES => [ glob("bin/*.pl") ],
    dist  => { COMPRESS => 'gzip -9f', SUFFIX => 'gz', },
    clean => { FILES => 'Graph-Undirected-Hamiltonicity-*.gz' },
);
[download]

In order to make a tarball for export to CPAN, then do: perl Makefile.PL && make && make manifest && make test && make dist

Warning: I am seriously cargo-culting with the above so there can well be a better/safer way.

bw, bliako