Shifted-Antimagic Labelings for Graphs: Exploration and Conjectures
Uncover the world of shifted-antimagic labelings for graphs through joint works by Zhishi Pan, Fei-Huang Chang, Hong-Bin Chen, and Wei-Tian Li. Delve into magic and antimagic labelings, exploring properties, conjectures, and examples in this intriguing mathematical realm.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Shifted-antimagic labelings for graphs Zhishi Pan Department of Mathematics Tamkang University Joint works:Fei-Huang Chang, Hong-Bin Chen and Wei-Tian Li 2019/8/20
Magic 9 4 2 7 3 8 5 6 1 Magic square
Magic labeling of graph Let ? = (?,?) is a simple graph [Sedl ek, 1963] A magic labeling is a function ? ?:? ? ?+ {0} s.t. ?,? ? ? , ? ?, ? ?(?)?(?) = ? ?(?)?(?) [Stewart, 1966] A magic labeling supermagic if the set of edge labels consisted of consecutive integers. ??is supermagic for ? 5 ? > 5 and ? 0 mod 4. Ex: ?6 8 1 2 11 6 10 14 15 5 13 3 9 7 12 4
Antimagic labeling [Hartsfield, Ringel, 1990] An anti-magic labeling of graph is a bijection ? ?:? ? {1,2, , ? } s.t. ?,? ? ? , ? ?, ? ?(?)?(?) ? ? ??(?). A graph ? is called antimagic if ? admits an antimagic labeling. ??(? 3), ??, ?? and ??(? 3) are antimagic. Ex: 1 1 3 10 12 1 3 4 1 2 2 3 5 7 9 4 3 2 1 3 2 6 8 7 5 4 6 8 9 10 15 18 3 8 11 12 4 5 12 78910 15 4 5 13 4 11 14 5 5 10 11 6 21 23 6 ?6 ?6 ?6 ?6
Antimagic labeling [Hartsfield, Ringel 1990] Conjecture: Every graph except for ?2are anti-magic. [Hartsfield, Ringel 1990] Conjecture: Every tree except for ?2are anti-magic. [Alon, Kaplan, Lev, Roditty, Yuster, 2004] All graphs with ?( 4) vertices and minimum degree log? are anti-magic. [Alon, Kaplan, Lev, Roditty, Yuster, 2004] If ? is a graph with ?( 4) vertices and the maximum degree ? ? 2, then ? is anti-magic. [Alon, Kaplan, Lev, Roditty, Yuster, 2004] All complete partite graphs except ?2are antimagic.
Antimagic labeling [Hefetz, 2005] A graph ? with 3?vertices is antimagic if it admits a ?3-factor. [Hefetz, Saluz, Tran, 2010] A graph with ??vertices, where ? is an odd prime and ? is positive, and a ??factor is antimagic. [Wang, 2005] If ? is an ?-regular antimagic graph with ? > 1 then ? ??is anti-magic. [Wang, 2005] The toroidal grids ??1 ??2 ???are antimagic. [Cheng, 2008] All Cartesian products or two or more regular graphs of positive degree are antimagic. [Cheng, 2007] ??1 ??2 ???(? > 2) and ?? ??are antimagic.
Antimagic labeling [Wang, Hsiao, 2008] The following graphs are anti-magic: ? ??(? > 1) and ? ?1,?where ? is regular; compositions ?[?] where ? is ?-regular with ? > 1; and the Cartesian product of any double star and a regular graph. [Solairaju, Arockiasamy, 2010] Various families of subgraphs of grids ?? ??are antimagic. [Liang, Zhu, 2013] If ? is ?-regular (? > 2), then for any graph ? with ? ? the Cartesian product ? ? is antimagic. 1 1, ? ? [Liang, Zhu, 2013] If ? ? odd degree, or ? has at least 2 ? ? antimagic. 1 and each connected component of ? has a vertex of 2 edges, then the prism of ? is ? ?
Antimagic labeling [Yilma, 2013] A connected graph with ? ? ? that if ? is a graph with ? = deg ? = ? ? and there exists a vertex ? in ? such that the union of neighborhoods of the vertices ? and ? forms the whole vertex set ?(?), then ? is antimagic. 3,|? ? | 9 is antimagic and ?, where ? |? ? |/3 [Cranston, 2009] For ? 2, every ?-regular bipartite graph is antimagic. [Liang, Zhu, 2014] Every cubic graph is antimagic. [Cranston, Liang, Zhu, 2015] Odd degree regular graphs are antimagic. [Chang, Liang, Pan, Zhu, 2016] Every even degree regular graph is antimagic.
?-shifted-antimagic labeling Let ? be a graph with |? ? | = ?. Given ? ?, if there exists an injective function ? from ?(?) to {? + 1,? + 2, ,? + ?} such that the vertex sums ??(?) are all distinct for all vertices ? ?(?), then we say ? is ?-shifted- antimagic and ? is a ?-shifted-antimagic labeling of ?. An antimagic graph is 0-shifted antimagic. Ex: 1 2 1 2 3 2 3 5 7 9 6 5 7 9 11 1-shifted-antimagic labeling 3 4 4 5 5 6 5 ?6
?-shifted-antimagic labeling Let ? be a graph with |? ? | = ?. Given ? ?, if there exists an injective function ? from ?(?) to {? + 1,? + 2, ,? + ?} such that the vertex sums ??(?) are all distinct for all vertices ? ?(?), then we say ? is ?-shifted- antimagic and ? is a ?-shifted-antimagic labeling of ?. An antimagic graph is 0-shifted antimagic. Problem: Is it true that for any graph other than ?2is ?-shifted-antimagic, for some a positive integer ?? Problem: Is it true that for any tree other than ?2is ?-shifted-antimagic, for some a positive integer ?? [Chang, Chen, Li, Pan, 2018] Every tree except for ?2is ?-shifted-antimagic for some ? ?. [Chang, Chen, Li, Pan, 2018] Every graph consists of vertices of odd degrees except for ?2is ?-shifted- antimagic for some ? ?.
?-shifted-antimagic labeling [Chang, Chen, Li, Pan, 2018] Every tree except for ?2is ?-shifted-antimagic for some ? ?. Lemma: Given a graph ?, if there exists an injective function ?:? ? {1,2, ,?}, s.t. ??? ??(?) whenever deg(?) = deg(?), for ? ?, then ? is ?- shifted-antimagic for any sufficiently large ?. 17 101 21 1 31 13 8 17 25 65 1 54 81 8 16 26 52 21 2 6 11 2 12 23 11 26 34 42 58 6 18 27 3 13 23 15 18 32 35 3 22 27 10 14 33 134 22 28 9 119 16 7 27 19 28 4 9 19 4 12 44 29 33 9 29 12 63 5 20 24 20 5 54 30
?-shifted-antimagic labeling [Chang, Chen, Li, Pan, 2018] Every tree except for ?2is ?-shifted-antimagic for some ? ?. Lemma: Given a graph ?, if there exists an injective function ?:? ? {1,2, ,?}, s.t. ??? ??(?) whenever deg(?) = deg(?), for ? ?, then ? is ?- shifted-antimagic for any sufficiently large ?. 18 105 23 2 32 14 9 18 26 58 67 2 85 9 17 27 55 22 16 3 12 3 24 12 27 35 44 60 7 19 28 4 26 16 19 33 36 4 23 28 11 15 36 138 23 19 29 123 8 29 20 29 5 10 20 5 13 46 30 34 10 30 13 65 6 21 25 21 6 56 31
?-shifted-antimagic labeling [Chang, Chen, Li, Pan, 2018] Every tree except for ?2is ?-shifted-antimagic for some ? ?. Lemma: Given a graph ?, if there exists an injective function ?:? ? {1,2, ,?}, s.t. ??? ??(?) whenever deg(?) = deg(?), for ? ?, then ? is ?- shifted-antimagic for any sufficiently large ?. 117 501 221 101 113 131 125 454 265 101 108 117 481 108 126 352 116 123 412 102 111 121 102 111 126 134 242 258 127 103 106 323 118 122 115 118 132 135 103 114 127 110 333 538 122 128 416 519 107 119 227 128 104 119 104 109 109 112 244 129 133 129 112 263 105 120 124 120 105 254 130
?-shifted-antimagic labeling [Chang, Chen, Li, Pan, 2018] Every graph consists of vertices of odd degrees except for ?2is ?-shifted- antimagic for some ? ?. Sketch proof:
?-shifted-antimagic labeling An antimagic labeling ? satisfying ??(?) < ??(?) whenever deg ? < deg ? , is called strongly antimagic. If ? is a strongly antimagic graph, then it is ?-shifted-antimagic for all ? 0. Consider for ? < 0 If ? is a ?-shifted-antimagic graph , then it is (? + ? + 1)-shifted-antimagic. If ? is a ?-shifted-antimagic graph for all integer ?, then ? is called absolutely antimagic. Every path ??with ? 6 is absolutely antimagic.
Graphs that are not ?shiftedantimagic Trees with diameter at most four For ? 2, the star ??is ?-shifted-antimagic if and only if ? { ? 2 1 , ? 2} A double star ??,?is absolutely antimagic if and only if ?,? {(2,1)} {(2? 1,1) | ? 1}. Moreover, ?2,1is ?-shifted-antimagic if and only if ? { 2, 3}, and ?2? 1,1is ?-shifted-antimagic if and only if ? (? + 1). The path ?5is ?-shifted-antimagic if and only if ? { 2, 3}.
Graphs that are not ?shiftedantimagic Disconnected graphs For any graph ?, there exists a constant ? = ?(?) such that the graph ? + ??3is not antimagic. 5? 2, 5? 2 The graph ??3is ?-shifted-antimagic if and only if ? { ? 2 1}. + 1 , , The graph 2?4is ?-shifted-antimagic if and only if ? { 2, 5}. The graph 2?3is ?-shifted-antimagic if and only if ? { 2, 5}.
Open problems Problem: Is it true that for any connected graph other than ?2is ?-shifted- antimagic, for sufficiently large integer |?|? Problem: Find a tree ? of diameter at least five which is not ?-shifted- antimagic for some integer ?. Problem: Find a graph ? containing a cycle, which is not ?-shifted- antimagic for some integer ?.
Thank you for your attention.
