Given that counting Hamiltonian cycles on bounded clique-width graphs will
suffice for our purposes, one result that is directly relevant is that of
Flarup and Lyaudet [1]}: They study the expressive power of Perfect
Matching and Hamiltonian polynomials of graphs of bounded clique-width
and show that they can simulate arithmetic polynomials, and are
themselves contained in \(\mbox{{\sf VP}}\) . This yields a \(\mbox{{\sf GapSAC}$^1$}\)  bound (implicit) for counting
Hamiltonian cycles in bounded clique-width graphs right away. There are two
aspects in which the work of [1]} differs from our work: Firstly,
even though their techniques are also inspired from [3]} like ours,
they work with a slightly different notion of clique-width namely
\(W-m-\mbox{clique-width}\)These are weighted versions of clique-width
and are used to produce weighted graphs.  [1]} motivate this variant of
clique-width by observing that since \(K_n\)  has clique-width 2, most graph
polynomials are \(\mbox{{\sf VNP}}\) -complete for bounded clique-width graphs.. Secondly,
in the case of counting Euler tours, from a straight-forward application of [1]}
the best upper bound that can be obtained from the circuit
families constructed in [1]} is non-uniform \(\mbox{{\sf GapSAC}$^1$}\) , whereas we get an upper bound of
Logspace-uniformIn an earlier version of this paper, we had erroneously
claimed a GapL upper bound for counting Euler tours. As pointed out to us by Ramprasad Saptharishi,
there is a rather serious gap with this approach. \(\mbox{{\sf \#SAC}$^1$}\) .
