Edge-Magic Total Labellings of Some Network Models
Hongyu WANG
1
, Bing YAO
1
*, Chao YANG
1
, Sihua YANG
1
, Xiang’en CHEN
1
,
Ming Yao
2
, Zhenxue Zhao
2
1
College of Mathematics and Statistics, Northwest Normal University, Lanzhou, 730070, China
2
Department of Information Process and Control,Engineering, Lanzhou Petrochemical College of
Vocational Technology, Lanzhou, 730060,
E-mail: yybb918@163.com,yybm918@163.com
Keywords: network; tree; set-ordered labellings; edge-magic total labelling; edge-symmetric
graphs
Abstract. It has been known that edge-symmetric graphs can be used as models of some scale-free
networks, such as hierarchial networks and self-similar networks, such as graph colorings can be
used for distinguishing objects of communication and informa-tion networks. We study the edge-
magic property of edge-symmetric graphs, and construct graphs having edge-magic total labellings
from smaller graphs.
Introduction
Graph coloring theory is one of the most actively branch in graph theory. It involves in many
fields, such as such as physics, chemistry, computer science, network theory, social science, etc.
And graph labelings provide useful mathematical models for a wide range of applications, such as
data security, cryptography (secret sharing schemes), astronomy, various coding theory problems,
communication networks, mobile telecommunication systems, bioinforma-tics and X-ray
crystallography. More detailed discussions on applications of graph labelings can be found in
Bloom and Golomb's papers [11] and [12]. Many studies in graph labeling refer to Rosa’s research
[13].
The mathematical model of scale-free networks in study of complex networks is closed to real
networks. It has been known that edge-symmetric graphs can be used as models of some scale-free
networks, such as hierarchial networks and self-similar networks, etc. Li et al. [18] critically
overviews the current understanding on scale-freeness and proposes its mathematically rigorous
definition of scale-free graphs. Yao et al. [19] present: The notation N(t) = (p(u, k, t),G(t)) denotes a
dynamic network, where p(u, k, t) is the probability such that the probability of a new node being
adjacent to k other nodes submits to p(u, k, t), G(t) is the connected topological structure (also,
graph) of N(t), t ∈[a, b]; G(a) is the initially connected graph of N(t) at t = a. We say a node of N(t)
an alltime-hub node if it is not a leaf of any spanning tree T(t) having maximal leaves in G(t) for
each time t∈[a, b]. By the method of analyzing spanning trees in scale-free networks, some
problems are researched in [20]. As a result, finding a spanning tree with as many leaves as possible
(MLATP is one of the classical NP-complete problems) is equal to finding a minimal connected
dominating set in a connected network. It is very important to make network models for simulating
real networks.
Sedlacek [14] published a paper about another kind of graph labeling, called the labeling magic.
His definition was motivated by the magic square notion in number theory. A magic labeling is a
function from the set of edges of a graph G into the non-negative real numbers, so that the sums of
the edge labels around any vertex in G are all the same. Stewart [15] called magic labeling
supermagic if the set of edge labels consisted of consecutive integers. Motivated by Sedlacek and
Stewart's research, many new related definitions have been proposed and new results have been
found.
Conjecture 1. [16] Every tree admits an edge-magic total labelling.
Conjecture 2. [17] Every tree admits a super edge-magic total labelling.
Applied Mechanics and Materials Vols. 347-350 (2013) pp 2752-2757
© (2013) Trans Tech Publications, Switzerland
doi:10.4028/www.scientific.net/AMM.347-350.2752
All rights reserved. No part of contents of this paper may be reproduced or transmitted in any form or by any means without the written permission of TTP,
www.ttp.net. (ID: 111.115.6.209-14/07/13,16:01:22)