反魔圖; Antimagic Graphs

NCU Institutional Repository > 理學院 > 數學系 > 研究計畫 > Item 987654321/47067

jsp.display-item.identifier=請使用永久網址來引用或連結此文件: http://ir.lib.ncu.edu.tw/handle/987654321/47067

题名:	反魔圖;Antimagic Graphs
作者:	林強;商珍綾
贡献者:	數學系
关键词:	數學類
日期:	2010-08-01
上传时间:	2011-07-13 16:25:25 (UTC+8)
出版者:	行政院國家科學委員會
摘要:	本計畫的在探究反魔圖(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
關聯:	財團法人國家實驗研究院科技政策研究與資訊中心
显示于类别:	[數學系] 研究計畫

文件中的档案:

档案	描述	大小	格式	浏览次数
index.html		0Kb	HTML	468	检视/开启

在NCUIR中所有的数据项都受到原著作权保护.

社群 sharing

数据加载中.....