山狀圖的最小秩

Abstract

對一以 1、2、...、n 為點的簡單圖 G 而言， 當一大小為 n 的實對稱矩陣滿足性質：此矩陣第 ij 位置非零若且唯若 i 與 j 在圖 G 上有邊， 則我們稱此矩陣與 G 相對應。一張圖的最小秩為其相對應的所有矩陣之最小的秩。在此論文中我們定義一種與一介於 2 與 n-1 間的數 m 有關的圖，命名為座落在 $m$ 的山狀圖。山狀圖含一 m 個點的路徑，其它 n-m 個點之間沒有邊相連，且它們連接到路徑的方式將路徑分成一些只在端點重疊的小段，每一小段為一點所獨佔，且該點至少有兩邊連接此小段。在此論文中，我們將證明一個座落在 m 的山狀圖其最小秩為 m-1。

Let G be a simple graph with vertex set V(G) = [n] = {1,2,..,n} and edge set E(G). The minimum rank m(G) of G is the minimum possible rank of an n by n symmetric matrix A whose i j-th entry is not zero if and only if ij is in E(G), where i,j are distinct. For m < n, a graph G with vertex set [n] is called a mountain based on [m] if G satisfies (i) the subgraph of G induced on {1,2,...,m} is a path which is partitioned into a few closed segments; (ii) each segment is assigned a unique vertex in [n]\[m] which has at least two neighbors in the closed segment; and (iii) all edges of G are either described in (i) or in (ii). In the thesis we show that a mountain based on [m] has minimum rank m-1: