谭学忠，谭学功

(1．广东商学院数学学院，广东广州510320;2．暨南大学华文学院，广东广州510610)

COLLATZ 和 SINOGOWITZ［3］首次提出了如下问题:刻划满足条件η(G)＞0的简单图．这个问题在化学中有重要应用，正如文献［4］所指，一个二部图G(对应于一个化学分子)如果满足条件η(G)＞0，那么表明这个图所代表的分子是不稳定的．后来其他特殊类型的简单图的零度也被广泛研究，但是符号图的零度问题却研究得很少，FAN等［5］首次考虑了符号图的零度问题，得到了单圈符号图的若干结论．本文将经典的简单图的特征多项式的系数定理做了推广，使其对符号图成立，并用它对单圈符号图的零度进行研究;定义了零指数集合的概念，得到单圈符号图的零指数集合，同时，对于文献［5］中的部分结论给出了不同的证明．

引理1［6］设是一个符号图．则是平衡的，当且仅当

这个引理表明，平衡的符号图与简单图是切换等价的．下面的引理则表明，非平衡的单圈符号图与一个底图相同，且圈中恰含一条负号边的单圈符号图切换等价．

引理2［7］设是一个非平衡的n阶单圈符号图．则 ^U切换等价于底图为U且圈中恰含一条负号边的单圈符号图．

本文推广了简单图的系数定理，并用它对符号树图和符号圈图的零度进行研究．同时，研究了单圈符号图的零指数集，并且确定零度为n-2、n-3和n-4的单圈符号图．

1 符号图系数定理及应用

对于简单图G而言，因为图G的零度等于其邻接矩阵A(G)的零特征值的代数重数，亦即A(G)的特征多项式中特征值0的重数，所以处理这个问题的重要工具是图谱理论中用以确定图G的特征多项式系数的著名定理——系数定理［8］．只要将这个定理稍作修改就可以得到相应的符号图的系数定理(见下面的定理1)．

证明 由文献［8］的等式(1．35)″，有

这里

根据符号图邻接矩阵的定义，初等图形 ^Cq中的一条负号边对)的贡献为-1，而则贡献2个1或2个-1(由的符号决定)，2种情况都等于(-1)2(这就是规定m()=2的道理)．所以结论成立． □

推论 1［5，8］设=(T，σ)，T 中的最大对集所含边数为q．那么η(^T)=n-2q．

应用定理1，可以得到底图为圈图的符号图的特征多项式的系数公式．

推论2 设

证明 由文献［8］的式(4．4)和定理1不难证明上述结论． □

推论2表明符号圈图的零度是0或者2，等价地说，符号圈图的秩为n或者n-2(见推论3)．

推论3［5］设是n阶符号圈图．那么

2 单圈符号图的零度与零指数集合

由于单圈符号图的底图是单圈简单图，所以其中包含一个符号圈图作为导出子图．下面用记号表示n(n≥3)阶单圈符号图的集合．本节考虑单圈符号图的零度和零指数集合问题．给出了零度等于n-2，n-3，n-4的图的刻画以及零指数集合，得到了当n≥4时的单圈符号图的零度上界为n-4．定理2的(1)、(2)以及定理4在文献［5］已经得到，我们在这里给出另一种证明方法．

接下来的证明要用到下面的引理:

引理3［5］如果符号图含有一个1度点，删去这个顶点及其邻接的顶点后导出的图设为 ^H，那么有)成立．

定理2［5］设是一个n阶单圈符号图，则

证明 由于(1)与(2)的证明是类似的，我们只证明(1)成立．首先，断言中不存在悬挂点．否则，设v)且 d(v)=1，N(v)=u．令{v，u}．那么，由引理3，=n-2．又因为η=n-2-r)，所以，r)=0，这说明是空图，从而，这与是单圈符号图矛盾．所以由推论3及条件n≥3知，n-2=2即n=4，所以同构于平衡的

定理3 n(n≥3)阶符号单圈图的零指数集为

当n≥5时，只需证明对于每一个0≤k≤n-4，都有一个单圈符号图满足

图1 零度等于k的图Figure 1 Graphswith nullity k

定理 4［5］设(n≥4)．那么-4当且仅当属于集合{非平衡的，非平衡的，其中是平衡的，而对和平衡性无限制．的底图见图2．

图2 零度等于n-4的单圈符号图Figure 2 Unicyclic signed graphswith nullity n-4

情形1:^G11的最小度为1．设v是中的1度点，且N(v)=w．删除v和w，设得到的图为记∪(n-n1-2)K1．由引理 3，有)=n-4．另外=n-4．这说明是空图．所以=(n1-2)K1．为了得到，恢复v，w到那么必为星图且∪ (n-n1-2)K1．最后将x和y恢复给需要将y和中的n-n1-2个孤立点中的每一个点连一条边．这得到另一个星图(n2=n-n1)．为了得到中的圈，需要在y和的某2个顶点之间各添加一条边．如果在y和的中心以及在y和的某个1度点各连一边，那么如果在中2个端点都选择1度点，那么上述证明过程表明，的平衡性对结论的成立没有影响．

［1］HARARY F．On the notion of balanced in a signed graph［J］．Michigan Math J，1953，2(1):143-146．

［2］GUTMAN I，LEE L S，SHEU JH，et al．Preicting the nodal properties ofmolecular orbitals by means of signed graphs［J］．Bull Inst Chem Acad Sinica，1955，42:25-32．

［3］COLLATZ L V，SINOGOWITZ U．Spektren endlicher grafen［J］．Abh Math Sem Univ Hamburg，1957，21:63-77．

［4］LONGUET H C．Resonance structures and MO in unsaturated hydrocarbons［J］．JChem Phys，1950，18:265-274．

［5］FAN Y Z，WANG Y，WANG Y．A note on the nullity of unicyclic signed graphs［J］．Linear Algebra Appl，2013，438:1193-1200．

［6］HOU Y P，LIJS．On the Laplacian eigenvalues of signed graphs［J］．Linear Multilinear A，2003，51:21-30．

［7］FAN Y Z，GONG SC，WANG Y，etal．Firsteigenvalue and first eigenvectors of a nonsingular unicyclic mixed graph［J］．Discrete Math，2009，309:2479-2487．

［8］CVETKOVIC D，DOOBM，SACHSH．Spectra of graphs［M］．New York:Academic Press，1980．