| 摘要: | 本計畫的在探究反魔圖(antimagic graph). 介紹如下：符號： 若G為一圖,f為從E(G)到R的函數,則f+為從V(G)到R的函數,且對 v∈ V(G), f+(v) Σ∈=)()(GEuvuvf 定義：G為一圖, (1) 若f為從E(G)到{1,2,………..,|E(G)|}的1-1函數,且f+ 為 1-1 ,則f 為G 的一個反魔標號. (1) 若 G 有一個反魔標號,則G為一個反魔圖. Hartsfield 及 Ringel 在1990年 [1] 提出下面的猜測. 反魔圖猜測：任何至少3個點的連通圖都是反魔圖. 在文獻中,下列圖形已被證明為反魔圖. (1) 路徑 Pn (點數n≧3), 迴路 Cn, 完全圖 Kn (n≧3). [1] (2) G×Cn 其中G 為 r-regular (r≧2) 且 antimagic. [2] (3) Pm×Cn , Pm×Pn. [3] (4) 完全n部圖, 滿足 △(G)≧|V(G)|-2 之圖G. [4] (5) 完全n支樹 (Complete n-ary tree). [5] (6) 有K3-factor 且點數為3k (k∈N)的圖. [6] (7) 規則二部圖(regular bipartite graph). [7] 反魔圖猜測並未完全解決. 第一年計畫工作目標. 證明下面圖形是反魔圖 1. 樹(tree) 2. Möbius grids 3. 森林(forests) 下面我們考慮一些反魔圖的一些變形定義：(1) 若f為G的反魔標號, 且滿足(degGv＜degGw⇒f+(v)＜f+(w)) 則f為G的degree–consistent反魔標號. (2) 若G有一個degree – consistent反魔標號, 則G為degree–consistent反魔圖. 定義：G為一圖, AR, 且|A|=|E(G)| ⊂ (1) 若 f為從E(G)到A之函數, f為一對一,且f+為一對一則f 為G 之A-反魔標號. (2) 若G有A-反魔標號,則G為A-反魔圖. 很明顯地, 圖G為反魔圖與圖G是{1,2,………..,|E(G)|}-反魔圖是同意義的. 定義：G為一圖, BR, |B||E(G)| ⊂ 若對任何AB,且|A|=|E(G)|, G都為A-反魔圖, 則稱G為B-反魔圖. ⊂ 我們知道： (1) Cycles及Kn (n≧3) 為R-反魔, Sn (n≧3)不是R-反魔. (2) path, double-stars, union of two stars, 及滿足△(G)=|V(G)|-1的圖形為 {0}∪R+-反魔圖第二年計畫工作目標. 我們將探討R-反魔圖, {0}∪R+-反魔圖, R+-反魔圖, 及 degree–consistent反魔圖. Antimagic graphs In this proposal, we will investigate antimagic graphs. Let’s begin with some notation and definitions. Notation. Let G be a graph and f be a function from E(G) to R. Then f+ is the function from V(G) to R such that f+(v) for v∈ V(G). Σ∈=)()(GEuvuvf Definition. Let G be a graph. (1) If f is a function from E(G) to {1,2,………..,|E(G)|} such that f is 1-1 and f+ is 1-1 , then f is an antimagic labeling of G. (2) If G has an antimagic labeling, then G is antimagic. Hartsfield and Ringel (1990) [1] proposed the following conjecture. Antimagic Conjecture. Every connected graphs of order≧3 is antimagic. In the literature , the following graphs are shown to be antimagic. (1) Path Pn of order≧ 3, cycle Cn , wheel, complete graph Kn (n≧3). [1] (2) G×Cn where G is r-regular (r≧2) and antimagic. [2] (3) Pm×Cn , Pm×Pn. [3] (4) Complete multipartite graph, graph G with maximum degree≧|V(G)|-2. [4] (5) Complete n-ary tree. [5] (6) Graph on 3k vertices (k∈N) with a K3-factor. [6] (7) Regular bipartite graph. [7] Antimagic Conjecture is far from being solved . Goal for the first year: Prove the antimagic property of the following graphs: 1. trees , 2. Möbius grids , 3. forests. We introduce some variations of antimagic labeling. Definition. Let G be a graph. (1) If f is an antimagic labeling of G such that f+(v)＜f+(w) for every pair of vertices v, w with degGv＜degGw, then f is a degree–consistent antimagic labeling of G. (2) If G has a degree–consistent antimagic labeling, then G is degree–consistent antimagic. Definition. Let G be a graph, and AR with |A|=|E(G)|. ⊂ (1) If f is a function from E(G) to A such that both f and f+ are 1-1 , then f is an A-antimagic labeling of G (2) If G has an A-antimagic labeling, then G is A-antimagic. Obviously, {1,2,………..,|E(G)|}-antimagic graph is the same as antimagic graph. Definition. Let G be a graph, and BR with |B| ≧|E(G)|. ⊂ If G is A-antimagic for every AB with |A|=|E(G)|, ⊂ then G is B-antimagic. We can see the following: (1) Cycles and Kn (n≧3) are are R-antimagic, and Sn the star with n edges (n≧2) is not. (2) Path, double-star, union of two stars, and graph G with maximum degree≧|V(G)|-1 are {0}∪R+-antimagic. Goal for the second year: We will explore R-antimagic, {0}∪R+-antimagic, and R+-antimagic graphs and degree-consistent antimagic graphs. 研究期間：9908 ~ 10007 |
