关于图的运算与图的Pfaffian性

关于一般的图的完美匹配计数的问题已证实是NP-hard问题.但Pfaffian图的完美匹配计数问题(以及其它相关问题)却能够在多项式时间内解决.由此可见图的Pfaffian性的重要性.在这篇文章中,我们研究了若干种影响图的Pfaffian性的运算.     

Extreme Hexagonal Chainswith Respect to Two Partial Orders

LetG=(VE)beagraPh-AsubsetMofEiscalledatnatchinyinGifnotwoelementsofMareadjacentinG.AmatchingMiscalledani-matchingiflMl=i,andapethetmatchingifIMI=lVl/2.AsubsetI0fViscalledanindePendentvertexsetifnotwoelementsofIareadjacentinG.AnindependeDtvertexsetIiscalledani-indePendentvertexsetiflII=i.Denotebym(G)thenumber0fperfectmatchingsinG,byp(G)thenUInerofmatchingsinG(=theHosoyaindex),bya(G)thenUInerofindependentvertexsetsinG(=theMerrilield-Simm0nsindex)-Ahexagonalsystemisa2-connectedp1a…     

最大Randid指标的k悬挂点化学树的性质

化学分子图G的Randie指标为R（G）=∑wv（dG（u）dG（v））^2/1．其中uv是G的边，dG（u）表示的顶点u的度．本文刻画了具有最大Randie指标的k悬挂点化学树的一些性质．     

两类四角系统的匹配数与点独立集数

给出了两类四角系统的完美匹配数、匹配数和点独立集数的计算公式     

最大特征根的极值六角链

定义了六角链的一种翻转-粘贴运算, 利用这一运算, 证明了Gutman 猜想.这一证明思想也可用于证明关于Hosoya指标和Merrifield-Simmons 指标的极值六角链的结果.     

最大Randi(c)指标的k悬挂点化学树的性质

化学分子图G的Randic指标为R(G)=E(dG(u)dG(v))-(1/2).其中uv是G的边,dG(u)表示G的顶点u的度.本文刻画了具有最大Randic指标的K悬挂点化学树的一些性质.     

一类3—连通图的周长

设G=(V,E)是一个n阶无向简单图,本文证明了:设G是一个3-连通图,若G的每一个最长圈是控制圈,则G的周长c(G)≥min{n,2NC_2}或G同构于Petersen图,其中NC_2={|N(u)∪N(v)||u,v∈V(G),d(u,v)=2}。     

渺位六角系统完美匹配Z——变换图

六角系统是2-连通的平面图，其每个内部面都是单位正六边形．六角系统的完美匹配是化学中苯类芳烃体系的Kekule结构．一个六角系统H完美匹配Z—变换图Z（H）是一个图，它的顶点集是H的完匹配集，两个匹配相邻当且仅当它们的对称差是一个单位正六边形．本文用乘积图刻划了沙位六角系统Z—变换图的结构．     

大次和的1－坚韧图中的最长圈

给一个图Ｇ，定义，是Ｇ的无关集，是Ｇ中使的无关集，本文证明了：设Ｇ是ｎ阶１－坚韧图，如果σｓ３≥ｎ。，则Ｇ包含长度至少为ｍｉｎ的圈。这个结果推广了若干已知结果，也解决了Ｂｒｏｅｒｓｍａ－Ｈｅｕｖｅｌ－Ｖｅｌｄｍａｎ所提猜想的一个特例．     

导出子图和周长的局部定理

设G是n阶2-连通图，3≤c≤n.本文绘出对于图G的每一个同构于K1.3或Z1的导出子图L，若d（u）且如果dL（u，v）=2有（v）=min{，|M3（u）|/2}这里M3（u）={v|dc（u,v）≤3}，则G包含长至少为c的圈．