; TeX output 2002.12.03:1904 vˍ:9color push Blackhtml:color push gray 0 color pop html:G color pop[(:9html: html:.MTvkcolor push Black color popZVg5PSfile=logo129.eps llx=0 lly=0 urx=99 ury=16 rwi=2880Bs獍Acolor push Black color popGN q cmbx12A
NoteontheT=otalNumZb erof ]Double
EulerianCircuitsinMultigraphs.s獒 ҁXQ ff cmr12V4alery/Liskovetscolor push rgb 1 0 0html:=K`y
cmr101 html: color pop 9 ;Institute/ofMathematics 7National/AcademyofSciences C220072,/Minsk WBelarus +html:color push cmyk 0 1 0 0߆T ff cmtt12liskov@im.bas-net.by html: color pop7
vcolor push Black color pop r!"V
3
cmbx10AbstractMƍlcolor push Black color pop-̻ K`y
3
cmr10Weeform!ulateexplicitlyanddiscussasimplenewenumerativeformulafordouble
_(directed)8euleriancircuitsin$b>
3
cmmi10n-edgedlabMeledm!ultigraphs.xTheformulafollowseasily_fromfarecen!t2-parametricformulaofB.MLass.>XQ cmr12MultigraphsBmaryhaveloSopsandareconsideredassymmetricmultidigraphs.
SSo,(inaneuleriancircuit,Bevreryedgeistraversedexactlyonceineachdirection(backtracksareallorwed).WithrespSecttoundirectedmrultigraphssuchcircuitsarecalledhere3@ cmti12double('euleriancirffcuits.AHmrultigraphQpSossessesadoubleeuleriancircuitifandonlyifitisconnected.WVedealZGwithlabffeledZGmrultigraphs,v/thatis,mrultigraphswithnumbSeredvertices.Moreover,v/anyvrertexYmaybSedistinguishedasarffoot.vIfamrultigraphisunroSoted,thenvertex1implicitlyplarystheroleoftheroSot.
color push Blackff ff -
^ٓR cmr71 html:color push gray 0 color pop html: SuppGortedUUinpartbytheINT*AS(GrantINT*AS-BELARUS97-0093) color pop :9color push Black 1G color pop *vˍ:9color push Blackhtml:color push gray 0 color pop html:G color pop[(-AllmdoubleeuleriancircuitsareconsideredasstartingandnishingattheroSot./Twro :9circuitsareeffquivalent~iftheydieronlyintheorderinwhicrhparalleledges(including:9loSops)orloopsinbothdirectionsaretrarversed.-WVedene(24g cmmi12n5!",
cmsy10 1)!!UR=(2n 1)(2n 3)531.8Ourmainresultisthefollorwing.:9 html: html: color push Black9N cmbx12Prop` osition 1 color popUUpE:toeffquivalence,ItheE:totalnumbffer"%2 cmmi8n ofdoubleeuleriancircuitsinmulti-0grffaphs35withnedgesisequaltofj(2n 1)!!ō3132n"|{Y cmr8+1/t 131[ z *k
G2(n+1)/U:.ߍIndeed,"bryatheoremofLass[html:color push cmyk 0 1 0 01 html: color pop],thenrumbSerofsucrhcircuitscolor push rgb 1 0 0html:22 html: color popinall:}h! cmsl12rootedmrultigraphswith6nedgesandmvrerticesis
m(2n 1)!!22m(K cmsy8 1@G6u
cmex10 ܍n v~aBm 1*G0B:6ݹSincetheverticesarelabSeled,thenrumbSerofrootingsisequaltom:Dividingtheaborveformulabymandsummingoverallmwrearriveatthedesiredexpression.h7
msam10 ThedzcorrespSondingnrumericalvXaluesof"n pfornUR=0;1;:::ʜ;8dzareasfollows:'f1,α2,13,150,2541,/57330,1623105,55405350,2216439225.ZThisisthesequenceA069736inSloane[html:color push cmyk 0 1 0 02 html: color pop].TheexpSonenrtialgeneratingfunctionis(p
lj z hԟ m91 2z-~ plj z hԟ m91 6z)=2z :Example.)enɹ=2::ԹThereare4unlabSeledconnectedmrultigraphswith2edges.A:graphon3gvrertices(path)withvertex1atanend(therearetwosuchgraphs)hasonlyonedoubleeulerianocircuit.ThesamegraphroSotedatthemiddlevrertexhastwocircuits.Thegraphconsistingdoftrwodverticesandtwoparalleledges(\lune")alsohastwodierentcircuits:(1a2%a+1b2Ww*b)ۃand(1a2Ww*b1b2%a+)whereaandbarethetrwoۃ(interchangeable)edgesconsideredasdirectedfrom1to2,DanduajandW/i*b>ιarethesameedgesintheoppSositedirection.XLikrewise,thegraphwithtrwoverticesandoneloSophasthreedoubleeuleriancircuitsifthevertexwiththeloSopislabeled1;LotherwisethecircuitisuniqueuptoequivXalence.aFinallyV,the1-vrertexgraphwithtwoloSopscontainsthreedierentcircuits:z(1a1%a+1b1Ww*b);(1a1b1%a1Ww*b)and(1a1b1Ww*b1%a+):So,thereare4+2+4+3UR=13doubleeuleriancircuitsinall.Remarks. 1.8Asymptotically"n grorwsasPC ܞn2 3=2܂62nR n!;whereC1=UR3=(2[Op
[O z ):2.vByTthesametheoremofLass,othetotalnrumbSerT"20RAn ٹofdoubleeuleriancircuitsinrooted labSeledZmrultigraphswithnedgesisequalto(2nx 1)!!32nP;numericallyZthisisthesequenceA011781[html:color push cmyk 0 1 0 02 html: color pop]:81;3;27;405;8505;229635;7577955;295540245; 3.ScIn~conrtrastwithtopSologicalmaps,5fewclosedformulaeareknownforthecountingofabstractgraphs(withoutisolatedvrertices)bythenumbSerofeffdges.
color push Blackff ff -
^2 html:color push gray 0 color pop html: SomeUUoftheabGoveUUdenitiondetailsareimplicitin[html:color push cmyk 0 1 0 01 html: color pop ]. color pop :9color push Black 2G color pop vˍ:9color push Blackhtml:color push gray 0 color pop html:G color pop[(:94.ArethereanrysimilarresultsforotherclassesofgraphsanddierenttypSesofequivXalence :9ofeuleriancircuits? :95.ǹArtrstglance,HitseemsasifwecouldusethesamemethoSdtocountdoubleeulerian:9circuits@regardlessofroSotingsinceevrerydoubleeuleriancircuithasoneandthesamenumbSer:9nofpSossiblestartingpairs(root,Dincidenrtedge).AccordinglyV,theconrtributiontothetotal:9sumlfromanryvertextakenastheroSotseemstobeproportionaltoitsvXalencyV.Thisidea,:9horwever,Ucan0ubSeseentofailbecauseofmrultipleedges,UloopsandthedenitionofequivXalence:9bSetrweenDPcircuits;q%cf.Etheexampleaborve.ENeverthelessDPnj"n 젹foroddn(atthesametime"n:9isoSddforevrenn;sothatndoesnotdivide"n whennisevren.)(V:9