Please use this identifier to cite or link to this item: http://hdl.handle.net/11455/97322
標題: 關於圖形之邊反魔方型態標號與缺數研究
Study on Graph Labeling and De ciency Problems of Edge-Antimagic Type
作者: 劉志璿
Chih-Hsiuan Liu
關鍵字: 圖形標號;(a,d)-邊反魔方標號;(a,d)-邊反魔方缺數;邊反魔方標號;邊反魔方缺數 µ;完全二部圖;完全圖;完全多部圖;graph labeling;(a, d)-edge-antimagic;edge-antimagic labeling;edge-antimagic deficiency;edge-antimagic deficiency µd(G);complete bipartite graph;complete multipartite graph;complete graph
引用: Bibliography [1] M. Ba ca Y. Lin, M. Miller, M. Z. Youssef, Edge-antimagic graphs, Discrete Mathematics, Volume 307, Issues 11-12, (2007), Pages 1232-1244. [2] M. Ba ca and M. Miller, Super Edge-Antimagic Graphs: A Wealth of Problems and Some Solutions. Brown Walker Press, Boca Raton (2008) [3] H. Enomoto, A. S. Llado, T. Nakamigawa, and G. Ringel, Super edge-magic graphs, SUT J. Math. 34 (1998) 105-109. [4] R. Figueroa-Centeno, R. Ichishima, and F. Muntaner-Batle, 'On the super edge- magic de ciency of graphs', Ars Combin., 78 (2006) 33-45. [5] R. Figueroa-Centeno, R. Ichishima, and F. Muntaner-Batle, 'The place of super edgemagic labelings among other classes of labelings', Discrete Mathematics, 231(2001),153-168. [6] J.A. Gallian, A Dynamic survey of graph labeling, Electronic Journal of Combi- natorics, (2017), #DS6. [7] N. Harts eld and G. Ringel, Pearls in Graph Theory, Academic Press, San Diego, 1990. [8] S. M. Hegde, S. Shetty, Strongly indexable graphs and applications, Discrete Mathematics 309(21): 6160-6168 (2009) [9] R. Ichishima and A. Oshima, The Super edge-magic de ciency and -valuations of graphs, J. Indones. Math. Soc. Special Edition (2011) pp. 59-69. 61 [10] A. Kotzig, On well spread set of integers, Publications du Centre de Recherches Mathematiques Universite de Montreal 161, (1972) [11] A. Kotzig and A. Rosa, Magic valuations of complete graphs, Centre de Recherches Mathematiques, Universite de Montreal, (1972) CRM-175. [12] A. Kotzig and A. Rosa, Magic valuations of nite graphs, Canad. Math. Bull., 13 (1970) 451-461. [13] J. Sedlacek, Problem 27, in Theory of Graphs and its Applications, Proc. Sym- posium Smolenice, June, (1963) 163-167. [14] B. M. Stewart, Magic graphs, Canadian J. Math., 18 (1966) 1031-1059. [15] B. M. Stewart, Supermagic complete graphs, Canadian J. Math., 19 (1967) 427-438. [16] T.-M. Wang, Toroidal grids are anti-magic, Computing and combinatorics, Lec- ture Notes in Comput. Sci., 3595, Springer, Berlin (2005) 671-679. [17] W.D. Wallis, Magic Graphs. Birkhauser, New York, NY, USA (2001)
摘要: 
圖形標號就是在圖形上的點、邊、或點和邊,同時安排整數,使其滿足特定的條
件。對一有限簡單圖G = (V,E),如果存在一對一的點標號f: V→{1, 2,….., |V|},
且邊e = uv 上標號w(e)定義為兩端點的點標號之和,即w(e) = f(u) + f(v),使得
邊標號成一等差數列a, a+d,……, a+(|E|-1)d,其中d 為正整數,則我們稱f 為一
個(a,d)-邊反魔方標號,圖G 為(a,d)-邊反魔方圖。圖形缺數概念為圖形標號的
推廣,計算圖形的缺數,即測量一圖形距離其標號存在性的遠近程度。若圖存在
標號,則缺數定義為零。眾所皆知,優美標號的缺數問題與工程上應用的最佳哥
隆尺具有密切的相關性。因此反魔方型態的圖形缺數問題研究,能促進在工程上
的更廣泛應用。我們考慮圖G 的(a,d)-邊反魔方缺數(G),即定義為放寬點
標號範圍至{1, 2, ……, |V|+k},使得圖形G 具有(a,d)-邊反魔方標號的最小整數
k 值,其中d 為正整數。更一般我們考慮圖G 的邊反魔方標號,即一對一點標
號f: V→{1, 2, ……, |V|},使得任意兩個邊e, e’的標號w(e) 和w(e’) 相異。相
關的邊反魔方缺數μ (G),即為放寬點標號範圍至{1, 2, ……, |V|+k},使得圖形
G 具有邊反魔方標號的最小整數k 值。在這篇論文中,對於所有的完全二部圖,
我們完全決定它們的(a,d)-邊反魔方缺數值,d≧1,以及邊反魔方缺數μ
值,同時我們也拓展至完全圖及完全多部圖的不同缺數結果。最後我們也列出更
多的待解問題。

A graph labeling is an assignment of integers to the vertices or edges, or both,
subject to certain conditions. A finite simple graph G = (V,E) is called (a,d)edge-antimagic if there exists an injective vertex labeling function f : V → {1,2,··· ,|V|}such that the edge labels{w(e) : e ∈ E} = {a,a+d,a+2d,······ ,a+ (|E|−1)d}, where d is a positive integer and the induced edge label is defined by w(e) = f(u)+f(v) for each e = uv ∈ E. One may consider the notion deficiency as a generalization of that of the graph labeling, which is a parameter measuring how
far a graph is away from the existence of the specific labeling. Note that if the graph
does not admit the labeling, then the deficiency is zero. It turns out the deficiency
problems of the well known graceful labeling are closely related to the Golomb rulers
with engineering applications. Therefore the study of the graph deficiency problems
of antimagic types hopefully contributes to more applications. The associated (a,d)
edge-antimagic deficiency µd(G) of a graph G = (V,E), which is defined as the
minimum integer k such that G is (a,d)-edge-antimagic by modifying the range of the injective vertex labeling function from{1,2,··· ,|V|}to{1,2,··· ,|V|+k}. More generally a graph is called edge-antimagic if there exists an injective vertex labeling function f : V →{1,2,··· ,|V|} such that the induced edge labels w(e) 6= w(e0) for any two edges e,e0 ∈ E. The associated edge-antimagic deficiency µ(G) of a graph G is similarly defined as the minimum integer k such that G is edge-antimagic by modifying the range of the injective vertex labeling function from {1,2,··· ,|V|} to {1,2,··· ,|V|+ k}. In this dissertation, among others we completely determine the (a,d)-edge-antimagic deficiency µd, d ≥ 1, and edge-antimagic deficiency µ of complete bipartite graphs Km,n. Also we extend the study of deficiency problems
to complete graphs and complete multi-partite graphs. More open problems and
future studies are posted.
URI: http://hdl.handle.net/11455/97322
Rights: 同意授權瀏覽/列印電子全文服務,2018-07-09起公開。
Appears in Collections:應用數學系所

Files in This Item:
File SizeFormat Existing users please Login
nchu-107-8098053005-1.pdf1.28 MBAdobe PDFThis file is only available in the university internal network    Request a copy
Show full item record
 
TAIR Related Article

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.