On the degrees of a strongly vertex-magic graph

C. Balbuena, E. Barker, K. C. Das, Y. Lin, M. Miller, J. Ryan, Slamin, Kiki Ariyanti, M. Tkac

Research output: Contribution to journalArticlepeer-review

15 Citations (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)539-551
Number of pages13
JournalDiscrete Mathematics
Volume306
Issue number6
DOIs
Publication statusPublished - 6 Apr 2006

Keywords

  • Degree
  • Graph
  • Labeling
  • Supervertex-magic

Fingerprint Dive into the research topics of 'On the degrees of a strongly vertex-magic graph'. Together they form a unique fingerprint.

Cite this