📂グラフ理論

アンダーソン-リビングストン定理の証明

要旨 ¹

$R$ この可換環が単位元$1$を持ち、その零因子の集合を$Z(R)$とするなら、その零因子グラフ$\Gamma (R)$は連結グラフであり、$\text{diam}(\Gamma (R)) \le 3$

---

• $\text{diam}$はグラフの直径を意味する。

説明

アンダーソンとリビングストンは、零因子グラフの研究における重要な功績を残しており、特にグラフの連結性と直径の上限値を特定するこの定理を、アンダーソン・リビングストン定理と呼ぶこともある。

証明

$x,y \in Z(R) (x \ne y)$とする。

• ケース1. $xy=0$
  当然、$d(x,y)=1$である。
• ケース2. $xy \ne 0$
  • ケース2-1. $x^2 = y^2 = 0$
    したがって、$d(x,y)=2$
  • ケース2-2. $x^2 = 0, y^2 \ne 0$
    $by=0$となる$b \in Z(R)$が存在する。
    • ケース2-2-1. $bx=0$
      したがって、$d(x,y)=2$
    • ケース2-2-2. $bx \ne 0$
      したがって、$d(x,y)=2$
  • ケース2-3. $x^2 \ne 0, y^2 = 0$
    ケース2-2と似ている。
  • ケース2-4. $x^2 \ne 0, y^2 \ne 0$
    $ax=0=by$となる$a, b \in Z(R)$が存在する。
    • ケース2-4-1. $a=b$
      $ax=0=ay$なので、$d(x,y)=2$
    • ケース2-4-2. $a \ne b$
      • ケース2-4-2-1. $ab=0$
        したがって、$d(x,y)=3$
      • ケース2-4-2-2. $ab \ne 0$
        したがって、$d(x,y)=2$

■