数理解析研究所講究録
第 1562 巻 2007 年 114-116

114

Some properties of an ideal based

zero-divisor graph1

金光三男 (Mitsuo Kanemitsu)
中部大学工学部
College of Engineering, Chubu University

零因子グラフの一番最初の研究は, 1988 年に I. Beck によって研究された可換環に付随した単純グラフの彩色数を中心とする研究であった. I.Beckも頂点の一つに入れて考察した. その後, 1999 年に DF.
は環の零元
Anderson と P.S. Livingston は は除外してその他の零因子を頂点集合を考察した. そとした (I.Beck の意味の) 零因子グラフの部分グラフ$0$$0$$,$$\Gamma(R)$の後 2003 年には, S.P. Redmond は可換環 $R$ のイデアル を使用してイについて研究した. イデアル $I=(0)$ にデアルによる零因子グラフ$I$$\Gamma_{I}(R)$による零因子グラフは, D.F. Anderson 達の定義した零因子グラフ他ならない.の特別な場合のイデアル $I=$
ここでは, 可換環 $R$ を整数環の剰余環についてこのグラフの固有多項式 $f(\lambda, Z_{n}, I)$$(a)$ による零因子グラフ
や異なる \downarrow サイクルの個数の係数とグラフの 2-マッチングの個数が 2 部グラフであるためとの関連について具体例で述べる. また,$\Gamma(R)$$Z_{n}$$\Gamma_{I}(Z_{n})$$n_{C}$$n_{M}$$\Gamma_{I}(Z_{n})$の特徴付けや, 超八面体グラフの異なる 4-サイクルの個数などについても考察する.の各元を頂点とし, 異なる 2 頂点の積が のときその 2 頂点は辺で結ばれていると定義したグラフを I.Beck による零定義 1 (I. Beck [2]).

因子グラフといい$0$$Z_{n}$$\Gamma_{0}(Z)$と書く.

定義(D.F. Andersomm and P.S. Livingston [1]).
体の集合 $Z(Z_{n})^{*}$ を頂点集合とし, 異なる 2 頂点の積が以外の零因子全のとき辺で結ばと記す.
れていると定義して出来るグラフを零因子グラフといい,
$2$

$0$

$0$

$\Gamma(Z_{n})$とする. 頂点集合は,$Z_{n}-I$ の元で\rangle $Z_{n}-I$ のある元 が存在して $ab\in I$ となるとき, を頂点とする. 異なる 2 頂点 $r,$ に対して, $rs=0$ のとき と は辺で結ばれて定義 3(S.P. Redmond [5]).

$Z_{n}$のイデアルを

$I$

$b$

$a$

$s$$a$$r$$s$

1This is a part of an abstract and details will be published elsewhere

115
いると定義したグラフを, イデアルと記す.

$II_{\sim}^{-}$

よる零因子グラフとい$A^{a},$$\Gamma_{I}(Z_{n})$への最短の道の長さとし, グラフ $G$ の直径
diam $(G)$ とは, 異なる 2 頂点の距離の上限をいう. 1 点だけからなるグラ
フのときは, diam $(G)=0$ とする.
また, グラフ $G$ の内周とは, $G$ における最短のサイクルの長さをい$gir(G)$ と記す. サイクルが無いときは, $gir(G)=\infty$ とする.
距離 $d(x$ , のは頂点$x$から$y$$Aa$

次に述べる.

$\Gamma_{I}(Z_{n})$が 2 部グラフであることを特徴付ける. このため, 補題を補題 1. イデアル による零因子グラフに長さ 2 の道 $a-x-b$が存在するとき, このグラフには長さ 4 のサイクルが存在するか, または$\{0, x\}$ がのイデアルである.
$I$$\Gamma_{I}(Z_{n})$$Z_{n}$

定理 2.の (0) でも素イデアルでもないイデアルを $I=(m)$とする.
が 2 部グラフである必要十分条件は次の (i) 又は (ii) がこのとき,が星グラフ (ii) $gir(\Gamma_{I}(Z_{n}))=4$ であり且成立することである. (i)
つが 2 部グラフである.
$Z_{n}$$\Gamma_{I}(Z_{n})$$\Gamma_{I}(Z_{n})$$\Gamma_{I}(Z_{m})$[4] において, 2-マッチングの個数を求める式を述べた.
定理 3 (Y. Jin and M. Kanemitsu [4]). $G$ が単純グラフで位数 で次数列を $(d_{1}, d_{2}, \cdots, d_{n})$ とする. このとき, 2-マッチングの個数は次式で求めることができる.
$n$$n_{M}$$n_{M}= \frac{1}{8}(\Sigma_{i=1}^{n}d_{i})^{2}-\frac{1}{2}\sum_{i=1}^{n}d_{i}^{2}+\frac{1}{4}\Sigma_{i=1}^{n}d_{i}$.

次数 $n$ のグラフ $G$ の固有多項式を $f(\lambda, G)=\lambda^{n}+C_{1}\lambda^{n-1}+C_{2}\lambda^{n-2}+$

よく知られているように, $C_{1}=0$ であり $C_{2}=$ -(グラフ $G$ のサイズ). また-(三角形の個数の 2 倍),$C_{4}=n_{M}-2n_{C}$ であることも知られている (例えば, $N.L$ . $Biggs[3|$ など).のどちらか
この事実を使用して 4-サイクルの個数か固有多項式の係数一方が分かれば他方も分かる.
容易に分かるように, $n=pq$ ($p,$ は互いに異なる素数) の場合は, イデア
ルによる零因子グラフは, $I=(0)$ の場合である, すなわち, 零因子グラフしか存在しない. このときのグラフ
は, 完全 2 部グラフ

$C_{3}\lambda^{n-3}+\cdots+C_{1}\lambda+C_{0}$とする.

$C_{3}$\rangle$=$$C_{4}$$q$$\Gamma_{I}(Z_{n})$$\Gamma(Z_{n})$$\Gamma(Z_{n})$116$K_{p-1,q-1}$となり, 固有多項式は, $f(\lambda, \Gamma(Z_{pq}))=\lambda^{p+q-2}-(p-1)(q-1)\lambda^{p+q-4}$であり, $n_{M}= \frac{1}{2}(p-1)(q-1)(pq-2p-2q+4),$ $n_{C}= \frac{1}{4}(p-1)(q-1)(pq-$$2p-2q+4)$ となる.
例. Z12 のイデアルは 6 個ある. それは (0),以外に, 2 個の素イデア
ルと $I_{4}=(4),$ $I_{6}=(6)$ である.
は完全グラフであり, 固有多項式は $f$ ( , Z12, ) $=\lambda^{3}-3\lambda-2$ . また(Z12) は完全 2 部グラフである. この完全 2 部グラフの固有多項式は $f$ ( , Z12, ).
$Z_{12}$$\Gamma_{I_{4}}(Z_{12})$$\lambda$$K_{3}$$I_{4}$$K_{2,4}$$\Gamma_{I_{6}}$$\lambda$$\Gamma(Z_{n})$$I_{6}$$=\lambda^{4}-8\lambda^{4}$の彩色数が 3 となる $n=9p$ の場合を定理の形でまとめておこう.

定理 4.

$p$

は 3 でない素数とする.

このとき,$\Gamma(Z_{9p})$の固有多項式$f(\lambda, \Gamma(Z_{9p}))=\lambda^{3p+5}-(12p-11)\lambda^{3p+3}-6(p-1)\lambda^{3p+2}+3(p-1)(14p-$$17)\lambda^{3p+1}$である. また, $n_{M}=12(p-1)(5p-7),$ $n_{C}=(p-1)(18p-33)$ .

から 個の隣接していない辺を超八面体グラフ
は, 完全グラフ取り除いて作られるグラフで完全多部グラフである. 次数列は$(2s-2))$ だから, $n_{M}=.s(s-1)(2s^{2}-6s+5),$ $n_{C}=$$((2s-2), (2s-2),$$K_{2s}$$H_{s}$$s$$K_{8,8,\cdots,S}$$\cdots,$$\frac{1}{2}s(s-1)(4s^{2}-16s+17)$.
参考文献[1] D.F.Anderson and P.S. Livingston, The zero-divisor graph of a commutative ring, J. Algebra 217 (1999), 434-447.

[2] I.Beck, Coloring of commutattive rings, J. Algebra 116, 208-226[3] N.L. Biggs, Algebraic Graph Theory, Cambrigde University Press,

1974.
[4] Y.Jin and M.Kanemitsu, Beck’s graphs as sociated withand theire
characteristic polynomials, to appear in Internationa J. of Applied Mathematics and Statistic.
$Z_{n}$[5] S.P.Redmond, An ideal-based zero-divisor graph of a commutativering, Comm. Algebra 31 (2003), 4425-4443.