史坦納三元系對應圖之最長導出路徑

Abstract

史坦納三元系是一個具有個 元素的區組設計 ， ，在集合 中找出一族三個元素的子集合(block) ，使得 中的任意兩元素都恰好包含於 中的一個集合。定義 為史坦納三元系之對應圖，將三元系中的每個block都視為一個點， ， 中任兩點相連的條件為它們只有一個共同的元素。 在這篇論文中，我們討論一個史坦納三元系對應圖的最長路徑問題。

A Steiner triple system of order v, STS(v), is a pair (X, B) where |X| = v and B is a collection of 3-element subset(blocks) of X such that each pair of elements in X occur together in a block exactly once. A Steiner triple system graph of (X, B) is defined to be a graph with vertex set B and two vertices are adjacent if and only if they have exactly one element in common. In this thesis, we study the longest induced path in obtained.