花苞圖的最小秩

Abstract

對一以[n]={1,2,...,n} 為點的簡單連通圖 G而言，當一大小為n的實對稱矩陣滿足性質：此矩陣非對角的第ij位置非零若且唯若i與j在圖G上有邊，則我們稱此矩陣與G相對應。一張圖的最小秩為其相對應的所有矩陣之中最小的秩。在此論文中我們定義一種與一介於1與n/4間的數m有關且點數為n的圖，命名為基於[n-m]的花苞圖。花苞圖含一個n-m點的環，其餘m個點之間沒有邊相連。環可以藉由切斷m邊將環分割成m段長度大於 2的區塊，使得這m個點各自與不同的區塊之間至少有3個邊相連。在此論文中，我們將證明一個基於[n-m]的花苞圖其最小秩為n-m-2。

For a simple graph $G$ of order $n$ with vertex set [n]=\{1,2,... ,n\}, an n by n real symmetric matrix A, whose ij-th entry is not zero if and only if there is an edge joined i and j in G, is said to be associated with G. The minimum rank of G is defined to be the smallest possible rank over all symmetric real matrices associated with G. A bud based on [n-m] is a graph G with vertex set V(G)=[n] satisfying the following axioms: 1. The subgraph of G induced on [n-m] is a cycle C_{n-m}, and the subgraph induced on [n]\ [n-m] has no edge. 2. The cycle C_{n-m} can be parted into m disjoints paths, and the length of these paths are at least 2. For all vertex v in [n]\[n-m], v has at least three neighbors in the same path. Any two vertices in [n]\[n-m] are not connected to the same path. In the thesis we will show that a bud based on [n-m] has minimum rank n-m-2.