TY - JOUR

T1 - On the degrees of a strongly vertex-magic graph

AU - Balbuena, C.

AU - Barker, E.

AU - Das, K. C.

AU - Lin, Y.

AU - Miller, M.

AU - Ryan, J.

AU - Slamin,

AU - Ariyanti, Kiki

AU - Tkac, M.

PY - 2006/4/6

Y1 - 2006/4/6

N2 - Let G=(V,E) be a finite graph, where |V|=n≥2 and |E|=e≥1. A vertex-magic total labeling is a bijection λ from V∪E to the set of consecutive integers {1,2,...,n+e} with the property that for every v∈V, λ(v)+∑w∈N(v)λ(vw)=h for some constant h. Such a labeling is strong if λ(V)={1,2,...,n}. In this paper, we prove first that the minimum degree of a strongly vertex-magic graph is at least two. Next, we show that if 2e≥10n2-6n+1, then the minimum degree of a strongly vertex-magic graph is at least three. Further, we obtain upper and lower bounds of any vertex degree in terms of n and e. As a consequence we show that a strongly vertex-magic graph is maximally edge-connected and hamiltonian if the number of edges is large enough. Finally, we prove that semi-regular bipartite graphs are not strongly vertex-magic graphs, and we provide strongly vertex-magic total labeling of certain families of circulant graphs.

AB - Let G=(V,E) be a finite graph, where |V|=n≥2 and |E|=e≥1. A vertex-magic total labeling is a bijection λ from V∪E to the set of consecutive integers {1,2,...,n+e} with the property that for every v∈V, λ(v)+∑w∈N(v)λ(vw)=h for some constant h. Such a labeling is strong if λ(V)={1,2,...,n}. In this paper, we prove first that the minimum degree of a strongly vertex-magic graph is at least two. Next, we show that if 2e≥10n2-6n+1, then the minimum degree of a strongly vertex-magic graph is at least three. Further, we obtain upper and lower bounds of any vertex degree in terms of n and e. As a consequence we show that a strongly vertex-magic graph is maximally edge-connected and hamiltonian if the number of edges is large enough. Finally, we prove that semi-regular bipartite graphs are not strongly vertex-magic graphs, and we provide strongly vertex-magic total labeling of certain families of circulant graphs.

KW - Degree

KW - Graph

KW - Labeling

KW - Supervertex-magic

UR - http://www.scopus.com/inward/record.url?scp=33645402535&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2006.01.019

DO - 10.1016/j.disc.2006.01.019

M3 - Article

AN - SCOPUS:33645402535

VL - 306

SP - 539

EP - 551

JO - Discrete Mathematics

JF - Discrete Mathematics

SN - 0012-365X

IS - 6

ER -