在无向图 G =< t,E X中,对于 G 的每一个节点 x,若 6 s = K,则称 G 为 K 正则的无向图； 设 D 为有向图,对于 G 的每一个节点 x,若6+ s = 6− s ,则称 D 为平衡有向图,x 为它的平衡点；在有向图 D 中,若6+  D   = 6−  D   = ð+  D   = ð+  D   = K,则称 D 为 K 正则有向图。[6,7]

3 图的伴随多项式最小根性质的应用

3。1 基本定义

定义 1 设 P(G,λ)表示图 G 的色多项式，称图 G 是唯一的，如果从 P(H, λ)= P(G, λ)可以 推出 H 和 G 同构。

定义 2 设任意图 G 的伴随多项式为 h(G、s)(简记为 h(G)): h(G、s)=  sg+b1(G) sg−1+b2(G) sg−2+⋯+bg−1(G)  s。

这里 g 为 G 的顶点数，bí(G)=N(G、g − í)，í = 0、1、⋯g − 1。N(G、K)表示 G 的 具有 K 个分支的理想于图的个数。

显然 b1(G)为图 G 的边数，若 b1(G)>0,定义 R(G)=b2(G)−

义 R(G)=0。注意：1 用Pn和Cn分别表示有几个顶点的路和圈；

b1  G  −1   +1；若 b (G)=0，则定

2

2  把K3的一个顶点与Pn−2的一个一度点重叠文献综述后所得的图记为Dn；

3 度序列为(1,1,1,2,⋯⋯,2,3)的 n 阶树记为Tn；

4 若G1与G2无公共顶点，则记其并图为G1  U G2；

5 用G表示 G 的补图。

3。2 基本引理

引理 1 设图 G 有 K 个分支：G1，G2，G3⋯Gk，则：R(G)=)í=1 R(Gí)。

引理 2 设 G 是 n 阶非平凡连通图，则：

（1）R(G)≤1,等号成立当且仅当 G ≅ Pn   n ≥ 2  或G ≅ K3；

（2）R(G)=0,当且仅当 G ≅ Cn 或 Dn 或 Tn(n≥ 4)。

引理 3[8]     用β  G  表示 h(G,s)的最小负实根，则有:

（i）β(Pn+1)  < þ(Pn),n ≥2。

（ii）β(Cn+1)  < þ(Cn),n  ≥4。

（iii）β(Dn+1)  < þ(Dn),n  ≥3。

（iν）β(Dn) < þ(Cn)< β(Pn),n ≥5。 引理 4   Cn(n≥5)是 伴随唯一的。