On the degrees of a strongly vertex-magic graph
- Authors: 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
- Relation: Discrete Mathematics Vol. 306, no. 6 (2006), p. 539-551
- Full Text: false
- Reviewed:
- Description: 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
- Description: C1
- Description: 2003001603
A lower bound on the order of regular graphs with given girth pair
- Authors: Balbuena, Camino , Jiang, T. , Lin, Yuqing , Marcote, Xavier , Miller, Mirka
- Date: 2007
- Type: Text , Journal article
- Relation: Journal of Graph Theory Vol. 55, no. 2 (2007), p. 153-163
- Full Text: false
- Reviewed:
- Description: The girth pair of a graph gives the length of a shortest odd and a shortest even cycle. The existence of regular graphs with given degree and girth pair was proved by Harary and Kovács [Regular graphs with given girth pair, J Graph Theory 7 (1983), 209-218]. A (
- Description: C1
- Description: 2003004727
Consecutive magic graphs
- Authors: Balbuena, Camino , Barker, Ewan , Lin, Yuqing , Miller, Mirka , Sugeng, Kiki Ariyanti
- Date: 2006
- Type: Text , Journal article
- Relation: Discrete Mathematics Vol. 306, no. 16 (2006), p. 1817-1829
- Full Text: false
- Reviewed:
- Description: Let G be a graph of order n and size e. A vertex-magic total labeling is an assignment of the integers 1, 2, ..., n + e to the vertices and the edges of G, so that at each vertex, the vertex label and the labels on the edges incident at that vertex, add to a fixed constant, called the magic number of G. Such a labeling is a-vertex consecutive magic if the set of the labels of the vertices is { a + 1, a + 2, ..., a + n }, and is b-edge consecutive magic if the set of labels of the edges is { b + 1, b + 2, ..., b + e }. In this paper we prove that if an a-vertex consecutive magic graph has isolated vertices then the order and the size satisfy (n - 1)
- Description: C1
- Description: 2003001604
Diameter-sufficient conditions for a graph to be super-restricted connected
- Authors: Balbuena, Camino , Lin, Yuqing , Miller, Mirka
- Date: 2007
- Type: Text , Journal article
- Relation: Discrete Applied Mathematics Vol. , no. (2007), p.
- Full Text: false
- Reviewed:
- Description: A vertex-cut X is said to be a restricted cut of a graph G if it is a vertex-cut such that no vertex u in G has all its neighbors in X. Clearly, each connected component of G - X must have at least two vertices. The restricted connectivity
- Description: C1
Improved lower bound for the vertex connectivity of (delta;g)-cages
- Authors: Lin, Yuqing , Miller, Mirka , Balbuena, Camino
- Date: 2005
- Type: Text , Journal article
- Relation: Discrete Mathematics Vol. 299, no. 1-3 (Aug 2005), p. 162-171
- Full Text: false
- Reviewed:
- Description: A (delta, g)-cage is a delta-regular graph with girth g and with the least possible number of vertices. We prove that all (delta, g)-cages are r-connected with r >= root(delta + 1) for g >= 7 odd. This result supports the conjecture of Fu, Huang and Rodger that all (delta; g)-cages are delta-connected. (c) 2005 Elsevier B.V. All rights reserved.
- Description: C1
- Description: 2003001397
On the connectivity of (k, g)-cages of even girth
- Authors: Lin, Yuqing , Balbuena, Camino , Marcote, Xavier , Miller, Mirka
- Date: 2008
- Type: Text , Journal article
- Relation: Discrete Mathematics Vol. 308, no. 15 (2008), p. 3249-3256
- Full Text: false
- Reviewed:
- Description: A (k,g)-cage is a k-regular graph with girth g and with the least possible number of vertices. In this paper we give a brief overview of the current results on the connectivity of (k,g)-cages and we improve the current known best lower bound on the vertex connectivity of (k,g)-cages for g even. © 2007 Elsevier B.V. All rights reserved.
- Description: C1