半正则二部图的补图生成树计数的一种新方法.pdf

Advances in Applied Mathematics A?,2024,13(2),606-611Published Online February 2024 in Hans.https:/www.hanspub.org/journal/aamhttps:/doi.org/10.12677/aam.2024.132059?K?)O?#XXX?,n?n&E?,vF2024c1?28FF2024c2?22FuF2024c2?29F?G=(U,V,E)?K?=?:8?:?G=(V1,V2,E)?y(V1,V2)?=V1 V2=V(G)V1 V2=eGv|V1|=s,|V2|=tui V1,dG(ui)=x(i=1,.,s),vj V2,dG(vj)=y(j=1,.,t)KG?K?PG=(s,t;x,y)|Kirchhoff?-n?Schur?K?)O?A?K?)8Oc?KKirchhoff?-nSchurA New Method for the Enumerattion ofthe Number of Spanning Trees of theComplement of a Biregular GraphJutian YaoSchool of Mathematical Information,Shaoxing University,Shaoxing ZhejiangReceived:Jan.28th,2024;accepted:Feb.22nd,2024;published:Feb.29th,2024:X.?K?)O?#J.A?,2024,13(2):606-611.DOI:10.12677/aam.2024.132059XAbstractA biregular(semiregular bipartite)graph is defined as a bipartite graph G=(U,V,E)for which erery two vertices on the same side of the given bipartition have the samedegree as each other.Let G=(V1,V2,E)be a connected bipartite graph with bipartition(V1,V2).V1V2=V(G)and V1V2=.If G satisfies|V1|=s,|V2|=t,and ui V1,dG(ui)=x(i=1,.,s),vj V2,dG(vj)=y(j=1,.,t),then G is a semiregular bipartite graph,denoted as G=(s,t;x,y).Based on the classical Kirchhoffmatrix-tree theorem,and byusing the Schur complement of a block of block matrix,we show a general expressionfor the number of spanning trees of the complement of a biregular graph G is given.As applications,several formulas for the number of spanning trees of the complementof various classes of biregular graph were obtainedKeywordsBipartite Graph,Semiregular,KirchhoffMatrix-Tree Theorem,Schur ComplementCopyright c?2024 by author(s)and Hans Publishers Inc.This work is licensed under the Creative Commons Attribution International License(CC BY 4.0).http:/creativecommons.org/licenses/by/4.0/1.?)8?C,=3|kX-A,3O!On9nz+A2.?53?-5,?)8?-5?-I.5,)?k-5 1.u?)On,;?OKirchhoff?-n 2,3,n?.d?K1?n 1?“f?)?8,p|/?)OK=zX“K;?;)O,k4O(|OFeussner|4:(G)=(G e)+(G/e),G?)8?uGe?fG e?)8G Te?fG/e?)8);d?,km?O,XG)?8G?TutteT(G;x,y)3x=1,y=1?AO 5.DOI:10.12677/aam.2024.132059607A?X?.G=(V(G),E(G),V(G)(PV)LG?:8,E(G)(PE)LG?8.?,?,i1T5L.eHGvV(H)=V(G),E(H)E(G),KHG?)f,PH G.eTG?)f,=V(T)=V(G),KTG?).G=(V,E)?)T1,T2?=?T1,T2?T1=T2(?),?:I.,P(G)LG)8.PKnn:?;sK2Ls1(?);Km,nL:8V(Km,n)yV1(|V1|=n)V2(|V2|=m)?.?G=(V1,V2,E)?y(V1,V2)?,=V1 V2=V(G)V1 V2=.eGv|V1|=s,|V2|=t,ui V1,dG(ui)=x(i=1,.,s),vj V2,dG(vj)=y(j=1,.,t),KG?K?,PG=(s,t;x,y).KnGLlKnGk?,G?Kn-.?|V(G)|=nKn GG?,PG.?M=ABCD#,Mp+q?,Ap?,Bp1q?,Cq1p?,Dq?.e?D_?,A BD1C f?DuM?Scur,PM/D.u?K?)?8,Spiro S 6 lA?K?)?O.?K?)OK,|?-n?Scur?K?)?O.2.nPG=(V,E),V=v1,v2,.,vn,E=e1,.,em.vi,vj V,evi,vj?,KPvi vj.NG(vi)=vj V|vi vj,di=dG(vi)=|NG(vi)|.?.d?L(G)=(lij)nnXe:lij=dii=j,1i 6=j,vi vj,0.Kirchhoff?-n 2LL(G)?“fG?)8,=(G)=(1)i+jdet(Li,j(G),Li,j(G)LlL(G)1i11j?f?.,eG=(V1,V2,E)(|V1|=s,|V2|=t)?KG?A(G)LXe/:A(G)=0B(G)BT(G)0#.p,B(G)=(bij)stG?vbij=(1vi vj,vi V1vj V23Gk;0.n2.1eM=aIk+bJk,va 6=0,a+bk 6=0,KM_DOI:10.12677/aam.2024.132059608A?XM1=1aIk+b(a+bk)aJk.ydudetM=a(k1)(a+bk)6=0,?M_(aIk+bJk)(1aIk+b(a+bk)aJk)=Ik,?(.n2.2(7,8)e?M=ABCD#,Mp+q?,Ap?,Bp1q?,Cq1p?,Dq?,e?D_?,M/DD3M?Scur,Kdet(M)=det(D)det(A BD1C)=det(D)det(M/D).(1)n2.3(9)?G=(V,E)(|V|=n),u=(ui)ni=1,v=(vi)ni=1Rn?,Kdet(L(G)+uvT)=nXi=1ui!nXi=1vi!(G).(2)3.)On3.1?G(s,t;x,y)-?K?,p,s+t=n.KG?G?)8(G)=(n x)sn2det?(n y)It1n xBT(G)B(G)?(3)y 5?G=Kn G.dn2.3det(L(Kn G)+Jn)=n2(Kn G)?(Kn G)=1n2det(L(Kn G)+Jn),qdL(Kn G)+Jn=L(Kn)L(G)+Jn,L(Kn)=nIn Jn,L(G)=xIsB(G)BT(G)yIt#,?L(Kn)L(G)+Jn=(n x)IsB(G)BT(G)(n y)It#,DOI:10.12677/aam.2024.132059609A?Xdn2.1n2.2,kdet(n x)IsB(G)BT(G)(n y)It#=(n x)s|(n y)It BT(G)(n x)Is)1B(G)|?det(L(Kn G)+Jn)=(n x)sdet?(n y)It1n xBT(G)B(G)?(Kn G)=(n x)sn2det?(n y)It1n xBT(G)B(G)?,y.f3.1?G=tK2,=G(t,t;1,1)-?K?.5?BT(G)B(G)=It,d(3),N?(tK2)=(n 1)tn2det?(n 1)It1n 1It?=n(t2)(n 2)t.f3.2?G=ki=1K1,y,=G(ky,k;1,y)-?K?,G?:8:Okyk,ky+k=n,5?BT(G)B(G)=yIk,d(3),N?(G)=(n 1)kyn2det?(n y)Ik1n 1BT(G)B(G)?=(n 1)kyn2det?(n y)Ikyn 1Ik?=(n 1 y)kn(k2)(n 1)(kyk).4.?(?K?)8?OK,|Kirchhoff?-nk?Scur?1?,?u?K?G?G?)8O?5(J,T(JLG?)OK?duG?k?1?OK,TO3A?z 10O(J?y,kM#5,?yN?25.DOI:10.12677/aam.2024.132059610A?X?a?P“K?uL6e5p?“6?8!/o0)?U8(urOBE ng?);?U)56)z1 Boesch,F.T.(1986)On Unreliability Polynomials and Graph Connectivity in Reliable NetworkSynthesis.Journal of Graph Theory,10,339-352.https:/doi.org/10.1002/jgt.31901003112 Kirchhoff,G.(1847)Ueber die Aufl osung der Gleichungen,auf welche man bei der Unter-suchung der linearen Vertheilung galvanischer Str ome gefjhrt wird.Annalen der Physik,148,497-508.https:/doi.org/10.1002/andp.184714812023 Biggs,N.(1993)Algebraic Graph Theory.2nd Edition,Cambridge University Press,Cam-bridge.4 Feussner,W.(1902)Ueber Stromverzweigung in netzf ormigen Leitern.Annalen der Physik,314,1304-1329.https:/doi.org/10.1002/andp.190231413205 Tutte,W.T.(1954)A Contribution to the Theory of Chromatic Polynomials.Canadian Journalof Mathematics,6,80-91.https:/doi.org/10.4153/CJM-1954-010-96 Spiro,S.(2019)Polynomial Relations between Matrices of Graphs.Journal of Graph Theory,90,288-303.https:/doi.org/10.1002/jgt.224017 Klee,S.and Stamps,M.T.(2019)Linear Algebraic Techniques for Weighted Spanning TreeEnumeration.Linear Algebra and Its Applications,582,391-402.https:/doi.org/10.1016/j.laa.2019.08.0098 Bapat,R.B.?M.?A,.M?T:M?T?,2014.9 Klee,S.and Stamps,M.T.(2020)Linear Algebraic Techniques for Spanning Tree Enumeration.The American Mathematical Monthly,127,297-307.https:/doi.org/10.1080/00029890.2020.170817110 Weinberg,L.(1958)Number of Trees in a Graph.Proceedings of the Institute of Radio Engi-neers,46,1954-1955.DOI:10.12677/aam.2024.132059611A?