蜘蛛圖的反魔方標號

Abstract

設圖G 是一由n 個點及m 條邊組成的有限簡單圖，圖G 的一個標號指的是在圖G 的每一個邊標上一個{1, 2, · · · ,m} 內的整數，且不同邊有不同標號。給定圖G 一個標號，定義每個頂點的頂點和是這個點所有連出去的邊的標號總和，若圖G 所有頂點的頂點和都不一樣，則稱此標號為反魔方標號；設f 是圖G 的一個反魔方標號，且對於任兩個度數不同的頂點u, v, deg(u) < deg(v)，若u 的頂點和嚴格小於v 的頂點和，則稱f 是圖G 的一個強反魔方標號。另外，若圖G 存在一個(強) 反魔方標號，我們稱G 是(強) 反魔方的。 反魔方標號一詞最早是由Hartsfield 和Ringel 提出，在他們的著作裡不只證明幾個簡單的例子(圈、路徑、輪子、完全圖等) 有反魔方標號，也同時提出所有不是K2 的連通圖都是反魔方的猜想。幾十年來， 陸陸續續有人證明滿足某些條件的圖有反魔方標號，但距離此猜想完全解決仍有很大的空間。 在本篇論文中，我們將範圍限縮到蜘蛛圖(有一個核心和至少三隻腳，每隻腳由數條邊組成)。由於這種圖已被證實具有反魔方標號，因此我們在這裡將證明一個更強的結果：所有的蜘蛛圖都有強反魔方標號。文章最後也會討論一些蜘蛛圖的變形是反魔方的。

Let G be a simple finite graph with n vertices and m edges. A labeling of G is a bijection from the set of edges to the set {1, 2, · · · ,m} of integers. Given a labeling of G, for each vertex, its vertex sum is defined to be the sum of labels of all edges incident to it. If all vertices have distinct vertex sums, we call this labeling antimagic. Suppose f is an antimagic labeling of G, and for any two vertices u, v with deg(u) < deg(v), if vertex sum of u is strictly less than vertex sum of v, then we say f is a strongly antimagic labeling of G. Furthermore, a graph G is said to be (strongly) antimagic if it has (a strongly) an antimagic labeling. The concept of antimagic labeling was first introduced by Hartsfield and Ringel. In their book, they not only proved that some graphs such as cycles, paths, wheels, complete graphs etc are antimagic, but also conjectured that all connected graphs other than K2 are antimagic. In the past years, graphs with some restriction were gradually poven to be antimagic, but this conjecture is still widely open. In this thesis, we restrict our graphs to spiders, which is a graph with a core and at least three legs, each leg contains some edges. Since all spiders have already been proven to be antimagic, we will prove a stronger result here, that is, all spiders are strongly antimagic. In the last chapter, we will discuss whether some variation of spiders are antimagic or not.