圖形的測地線數

Abstract

本文所討論的圖形均為簡單圖，即頂點個數為有限、邊的兩端點不一樣、邊沒有方向、以及兩個頂點之間最多只有一條邊。 對圖形G裡的任意兩個頂點u和v，集合I（u, v）為包含了u和v，以及所有位於長度為d（u, v）、端點為u和v的路徑上面的所有頂點的集合。如果S是一個頂點的子集合，則I（S）表示所有任意在S裡的兩個點u和v所構成的I（u, v）的聯集。如果I（S）剛好就是所有的頂點的話，我們就稱S為測地線集。而測地線數，g（G），就是最小的測地線集的大小。 在第一節我們介紹一些本論文所用及的定義。 第二節我們將討論圖形迪氏積的測地線數，主要的結果是對任意兩個圖形都有 g（G）≦ g（G□H），且在一些特殊的條件下等號會成立。 第三節則討論到補可簡化圖的測地線數的上界。並且我們定義了2-N-支配，一個2-N-支配集D的定義是任意一個不在集合D裡的頂點v，必有兩個不相鄰的鄰居在集合D裡面，而2-N-支配數則是最小的2-N-支配集的大小。並討論一些測地線數和2-N-支配數的等價關係。 第四節討論到樹形補可簡化圖的測地線數的上界，還設計了一個演算法來求在一個樹形圖上的2-N-支配數。

All graphs in this thesis are simple, i.e., finite, undirected, loopless and without multiple edges. For any two vertices u and v of a graph G, a u-v geodesic is a path of length d(u, v). The set I(u, v) consists of all vertices lying on some u-v geodesic of G.. If S is a subset of V(G), then I(S) is the union of all sets I(u, v) for u and v in S. The geodetic number g(G) is the minimum cardinality among the subset S of V(G) with I(S)=V(G). In section 1, we introduce some definitions, which is used in this thesis. In section 2, we discuss geodetic numbers on Cartesian products of graphs. The main result is g(G) ≦ g(G□H) for any two graphs G and H. And g(G)=g(G□H) for some H with some special condition. In section 3, we discuss an upper bound of geodetic numbers of cographs. A 2-N-dominating set of a graph G is a vertex subset D such that every vertex not in D is adjacent to two distinct non-adjacent vertices in D. Denote by g2(G) the minimum cardinality of a 2-N-dominating set in G. And we discuss the relation between geodetic numbers and 2-N-domination numbers. In section 4, we define tree-cographs and term f-domination. And we design an algorithm to find the 2-N-domination number of a tree-cograph.