; TeX output 2000.06.08:0025 KE&:9color push Blackhtml:color push gray 0 color pop html:G color pop3ڍ:9|&html: html:.MTcolor push Black color popZVg4PSfile=logo26.eps llx=0 lly=0 urx=99 ury=16 rwi=2880*
FN G cmbx12CounutingzSetCoversandSplitGraphs8Gu qXQ cmr12GordonF.Roryle ]K`y
3
cmr10Departmen!tfofComputerScience
Univ!ersityfofWeesternAustralia andwvDepartmen!tfofCombinatoricsandOptimization Univ!ersityfofWeaterloMo Emailfaddress:+html:color push cmyk 0 1 0 0gordon@cs.u!wa.edu.au color pop html:Q r"V
3
cmbx10Abstract ':
3
cmti10APbijepctionPbetweensplitgraphsandminimalcoversofasetbysubsetsispresented.;CAstheenu-merpationfproblemforsuchminimalcovershasbeensolved,thisimpliesthatsplitgraphscanalsobpeenumerated.Ahtml: html:1}MotivLationqA/sp0J
3
cmsl10split/graphisac!hordalgraphwithachordalcomplement.AItisstraightforwardtorecognizesplitgraphs,andrthereforetocomputethen!umbMersrofsplitgraphsonasmalln!umberrofv!ertices,assho!wninTeablehtml:color push cmyk 0 1 0 01 color pop html:.Wheneversuchatableisgiven,.
itistobMeunderstoodthattheycon!tainnumbMersof{pairwisenon-isomorphicob jects,.ratherthan`labMeled'objects.^#Then!umbMers{inTeable1formsequenceAehtml:color push cmyk 0 1 0 0A48194 color pop html:in[html:color push cmyk 0 1 0 05 color pop html:y],hkwhic!hisanonlinedatabaseofinterestingsequencesofintegers(seealso[%html:color push cmyk 0 1 0 04 color pop html:y]).OnemoftheaimsofthisdatabaseistopMermitresearc!herswhoencounterasequencetodeter-mine+
whetherithasoMccurredbefore,L6andinwhatcon!text,thereby+
expMosingpossiblyunexploredconnections. Ab>
3
cmmi10kX?-co!verofann-setN>isacollectionofke2subsetsofNwhoseunionisN1.AkX?-co!verisminimalifnosub-collectionalsoco!versN1.Clarke[html:color push cmyk 0 1 0 01 color pop html:y]givesanexpressionforthenumbMerofminimalkX?-coversofann-set(whereagainitistobMeunderstoodthatthen!umbersrefertothen!umberofpairwisenon-isomorphicaob jects).Usingthisform!ula,MichaelaSomos(privdDatecomm!unication)computedthe$totaln!umbMer$ofminimalco!vers$ofann-setandusing[html:color push cmyk 0 1 0 05 color pop html:y]observ!edthatforn(!",
3
cmsy1011$(thelimitofJthesequencekno!wnatthattime),sthisnumbMerwasequaltothenumbMerofsplitgraphsonnv!ertices. Thefcurren!tpapMershowsthatthisisnocoincidencebyprovingthefollowingresult: :9color push Black #1G color pop *KE&:9color push Blackhtml:color push gray 0 color pop html:G color pop3ڍ&:91.1Y&-
3
cmcsc10Theorem.QThereisaone-onecorrespMondencebet!weenYthesplitgraphsonnv!erticesandthe
:9minimalfco!versofasetofsizen. ":98color push Black "㍍ y!vk ff z ͟}
ff͟냹Veertices7SplitfGraphs͟}
ffz ff z͟}
ffk1oUk1͟}
ff
͟}
ffk2oUk2͟}
ff͟}
ffk3oUk4͟}
ff͟}
ffk4oUk9͟}
ff͟}
ffk5i21͟}
ff͟}
ffk6i56͟}
ff ff z ͟}
ffk7db7164͟}
ff͟}
ffk8db7557͟}
ff͟}
ffk9^2223͟}
ff͟}
ff:10Yo10766͟}
ff͟}
ff:11Yo64956͟}
ff͟}
ff:12Si501696͟}
ff ff zircolor push BlackTeablef1:html:color push gray 0 color pop html:Splitgraphsonsmalln!umbMersfofv!ertices color pop color pop:9Ahtml: html:2}BactkgroundqIn69thispapMer,Lagraphmeansanundirectedgraphwithoutm!ultipleedgesorloops.yFeorbasicgraphtheoryfterminologyandbac!kground,thebMooksfofDiestel[html:color push cmyk 0 1 0 02 color pop html:y]andWeest[html:color push cmyk 0 1 0 06 color pop html:]arerecommended. AYgraphاisc!hordalF(ortriangulated)ifithasnocycleoflength4orgreaterasaninducedsubgraph.Chordal!graphsformanimpMortan!tclassofgraphs,andhavebMeenextensivelystudied,particularlyTwithrespMecttodeterminingthecomplexit!yofawiderangeofproblemsknowntobMe`NP-hardforgeneralgraphs.ARsplitgraphisac!hordalgraphwithachordalcomplement;]thisterminologyAarisesbMecauseagraphX9isasplitgraphifandonlyifthereisapartitionVn(X )
=I[ ȣCwhere ^IVisanindepMenden!tsetandC߹aclique(seeFeoldes&Hammer[$html:color push cmyk 0 1 0 03 color pop html:y]).KThusXVcanbMe`split'in!tohacliqueandanindepMendentset|asplitVn(X )
=IC[KC0willhbMecalledspecialifev!eryvertexinCHisadjacen!ttoatleastonevertexinI .EverysplitgraphhasaspMecialsplit,Ibecauseifthereisav!ertexfinCnnotadjacenttoanyelementofI ,itcanbMemovedtoI . In{generalakX?-co!ver{ofann-setma!yincludebMothemptysetsandmultipleoMccurrencesofasubset.The^/kX?-co!versSz|{Y cmr813ofNz1andSz2ofNz2areisomorphicifthereisabijection
:Nz1ʫ7!Nz23suc!hthatI(Sz1)M =Sz2.UClark!eI[html:color push cmyk 0 1 0 01 color pop html:y]considersseveralenumerationproblemsforkX?-covers.UHeencompassesthe&situationswheretheco!ver&isorderedorunordered,ޖminimalornot-necessarilyminimalandcoun!ting@isdonebMothbytotalnumbMersornumbMersofisomorphismclasses.4kHoweverwewillonlyneedtousethen!umbMerofisomorphismclassesofminimalco!vers|whatClarketerms`minimaldisorderedKunlabMeledco!vers'.*FigureKhtml:color push cmyk 0 1 0 01 color pop html:sho!wsaminimal4-coverofa9-set|inamanneranalogoustofdra!wingagraphitrepresentsanisomorphismclass,ratherthana`labMeled'cover. Giv!enacoverS9=
fSz1;1:::l;1SȮ2 cmmi8k#g,wedeneanelementa
2N_tobMeloyalifitliesinonlyoneofthefsubsetsSzidڹ.IfSGisaminimalco!ver,fthenev!erysubsetSzi@containsaloyalelement.Rhtml: html: :9color push Black #2G color pop KE&:9color push Blackhtml:color push gray 0 color pop html:G color pop3ڍэ:9EUcolor push Black}EU? <