Completely Separating Systems and Antimagic Labeling of Regular and Non-Regular Graphs

Kdy? 21.9.2010 10:15 - 11:15
Kde? ZČU / FAV / KMA / UL610 (učebna)
Kategorie

Oudone Phanalasy: Completely Separating Systems and Antimagic Labeling of Regular and Non-Regular Graphs

 

Abstract:

A vertex antimagic edge labeling of a graph with q edges is a bijection from the set of edges to the set of positive integers {1, 2, . . . , q} such that all vertex weights are pairwise distinct, where the vertex weight of a vertex is the sum of the labels of all the edges incident with that vertex. A graph is antimagic if it has a vertex antimagic edge labeling.


In 1990, Hartsfield and Ringel conjectured that every graph with the exception of K2 is antimagic. During the last two decades there have been many attempts to prove this conjecture.


In this talk we will describe our novel method for constructing vertex magic edge graph labeling using ‘completely separating systems’.


Let [n] = {1, 2, . . . , n}. A completely separating system (CSS) on [n] (or (n)CSS), is a collection C of subsets of [n] in which for each pair of elements a 6= b ∈ [n], there exist A,B ∈ C such that a ∈ A, b /∈ A and b ∈ B, a /∈ B. Using completely separating systems as a tool for studying labeling of graphs, we show that there is a relationship between CSSs and antimagic labeling of graphs. Moreover, combining this relationship with various graph operations, we construct vertex antimagic edge labelings for various families of both regular and non-regular graphs, thereby giving further support to the Hartsfiels-Ringel conjecture.

Evropská unie, ESF, MŠMT, OP Vzdělávání pro konkurenceschopnost, ZČU

Vyhledávání

RSS kanál

Chcete mít stále aktuální přehled toho, co se chystá? Přidejte si náš kanál s přehledem chystaných událostí do Vaší RSS čtečky.