完全多部圖之線性k蔭度

Abstract

如果圖形G的一些子圖能讓G的每一個邊恰好只出現在它們的其中之一，則這些子圖被稱為是圖形G的一個分解。到目前為止，在圖形的分解這個研究領域上，已經有不少有趣的結果和問題被發表。而這篇論文所要探討的是其中的一個問題，我們稱做是線性k蔭度問題。

一個完全由長度不大於k的路徑所構成的圖形，我們稱之為線性k森林。而一個圖形G所能分解成線性k森林的最少數量則稱為圖形G的線 性k蔭度。因此，當一個圖形給定後，它的線性k蔭度為何，就是我們所謂的線性k蔭度問題。

對於線性k蔭度所闡述的概念，我們可以將之視為圖形理論裡邊著色課題的一種延伸性想法，以及對線性蔭度課題更深入詳盡的探究。而所謂的線性蔭度，其實是將線性k蔭度的定義裡有關於路徑長度的限制去除。

在西元1982年，針對一個圖形G的線性k蔭度的上界，有兩位學者提出了一個重要猜測。而對於這個猜測的驗證，迄今也發表了許多的結果在文獻裡。譬如當圖形G是一個立方圖、一個樹、一個完全圖、或者是一個均衡完全二部圖，以及某些特定的k值。

在這篇論文裡，我們會確定均衡完全二部圖、完全圖、和部份的均衡完全多部圖的線性3蔭度。同時，對於部份的完全二部圖、完全圖、和均衡完全多部圖，我們也會提供它們的線性2蔭度的值。而所有我們獲得的結果，在相同的條件下，會剛好驗證上述的猜測。

此外，在這篇論文裡，我們還探討了一個關於位元排列網路的問題。我們會證明從一個位元排列網路N的有向線圖所建構出的新網路 G(N)^{+}，它的結構將依然是一個位元排列網路。我們也會給定一個簡易的運算式，它能夠從N的特徵向量來導出G(N)^{+}的特徵向量。這個運算式可以幫助我們去獲得位元排列網路彼此之間的關聯性。

A decomposition of a graph is a list of subgraphs such that each edge appears in exactly one subgraph in the list. There are many interesting results and problems in this area. In this thesis, we study a special case of graph decomposition, called the linear k-arboricity problem.

A linear k-forest is a graph whose components are paths with lengths at most k. The minimum number of linear k-forests needed to decompose a graph G is the linear k-arboricity of G, denoted la_{k}(G). Thus, the linear k-arboricity problem is what the value la_{k}(G) should be when a graph G is given.

The notion of linear k-arboricity is a natural generalization of edge coloring and also a refinement of the concept of linear arboricity in which the paths have no length constraints.

In 1982, Habib and Peroche made an important conjecture about the upper bound of the linear k-arboricity of a graph G. So far, in the literature, quite a few results on the verification of this conjecture have been obtained. For example, when G is a cubic graph, tree, complete graph, or balanced complete bipartite graph, and some values of k.

In this thesis, we determine the linear 3-arboricity of balanced complete bipartite graphs, complete graphs, and parts of balanced complete multipartite graphs. We also give some substantial results about the linear 2-arboricity of complete bipartite graphs, complete graphs, and balanced complete multipartite graphs. The results obtained are coherent with the corresponding cases of the conjecture mentioned above.

Furthermore, in this thesis, we study a problem on the bit permutation network. We prove that if N is an s-stage d-nary bit permutation network with d^{n} inputs (outputs), then a new network L(N)^{+} obtained from the line digraph of N is an (s+1)-stage d-nary bit permutation network with d^{n+1} inputs (outputs). We also give a simple (but not trivial) formula to determine the characteristic vector of L(N)^{+} from the characteristic vector of N. This formula can help us to obtain relations between some well-studied bit permutation networks.