On k -minimum and m -minimum edge-magic injections of graphs

• Published in: Discrete mathematics 2010-01, Vol.310 (1), p.56-69
• Main Authors: McSorley, John P., Trono, John A.
• Format: Article
• Language: English
• Subjects: [formula omitted]-minimum [formula omitted]-sequence; [formula omitted]-sequence; Algorithmics. Computability. Computer arithmetics; Applied sciences; Combinatorics; Combinatorics. Ordered structures; Computer science; control theory; systems; Double-witness; Edge-magic injection; Exact sciences and technology; Graph theory; Information retrieval. Graph; Magic strength; Mathematics; Sciences and techniques of general use; Theoretical computing; Well Spread-sequence
• ISSN: 0012-365X; 1872-681X
• DOI: 10.1016/j.disc.2009.07.021

An edge-magic total labelling (EMTL) of a graph G with n vertices and e edges is an injection λ : V ( G ) ∪ E ( G ) → [ n + e ] , where, for every edge u v ∈ E ( G ) , we have w t λ ( u v ) = k λ , the magic sum of λ . An edge-magic injection (EMI) μ of G is an injection μ : V ( G ) ∪ E ( G ) → N with magic sum k μ and largest label m μ . For a graph G we define and study the two parameters κ ( G ) : the smallest k μ amongst all EMI’s μ of G , and m ( G ) : the smallest m μ amongst all EMI’s μ of G . We find κ ( G ) for G ∈ G for many classes of graphs G . We present algorithms which compute the parameters κ ( G ) and m ( G ) . These algorithms use a G -sequence: a sequence of integers on the vertices of G whose sum on edges is distinct. We find these parameters for all G with up to 7 vertices. We introduce the concept of a double-witness: an EMI μ of G for which both k μ = κ ( G ) and m μ = m ( G ) ; and present an algorithm to find all double-witnesses for G . The deficiency of G , d e f ( G ) , is m ( G ) − n − e . Two new graphs on 6 vertices with d e f ( G ) = 1 are presented. A previously studied parameter of G is κ E M T L ( G ) , the magic strength of G : the smallest k λ amongst all EMTL’s λ of G . We relate κ ( G ) to κ E M T L ( G ) for various G , and find a class of graphs B for which κ E M T L ( G ) − κ ( G ) is a constant multiple of n − 4 for G ∈ B . We specialise to G = K n , and find both κ ( K n ) and m ( K n ) for all n ≤ 11 . We relate κ ( K n ) and m ( K n ) to known functions of n , and give lower bounds for κ ( K n ) and m ( K n ) .