- Title
- On the degrees of a strongly vertex-magic graph
- Creator
- Balbuena, Camino; Barker, Ewan; Das, K. C.; Lin, Yuqing; Miller, Mirka; Ryan, Joe; Slamin,; Sugeng, Kiki Ariyanti; Tkac, M.
- Date
- 2006
- Type
- Text; Journal article
- Identifier
- http://researchonline.federation.edu.au/vital/access/HandleResolver/1959.17/53661
- Identifier
- vital:92
- Identifier
-
https://doi.org/10.1016/j.disc.2006.01.019
- Identifier
- ISSN:0012-365X
- 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. © 2006 Elsevier B.V. All rights reserved; C1
- Publisher
- Elsevier
- Relation
- Discrete Mathematics Vol. 306, no. 6 (2006), p. 539-551
- Rights
- Copyright Elsevier
- Rights
- This metadata is freely available under a CCO license
- Subject
- 0101 Pure Mathematics; Labeling; Supervertex-magic; Computational complexity; Hamiltonians; Integer programming; Set theory; Graph theory
- Reviewed
- Hits: 8147
- Visitors: 8057
- Downloads: 1
| Thumbnail | File | Description | Size | Format |
|---|