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
All (k;g)-cages are edge-superconnected
- Authors: Lin, Yuqing , Miller, Mirka , Balbuena, Camino , Marcote, Xavier
- Date: 2006
- Type: Text , Journal article
- Relation: Networks Vol. 47, no. 2 (2006), p. 102-110
- Full Text: false
- Reviewed:
- Description: A (k;g)-cage is k-regular graph with girth g and with the least possible number of vertices. In this article we prove that (k;g)-cages are edge-superconnected if g is even. Earlier, Marcote and Balbuena proved that (k;g)-cages are edge-superconnected if g is odd [Networks 43 (2004), 54-59]. Combining our results, we conclude that all (k;g)-cages are edge-superconnected. © 2005 Wiley Periodicals, Inc.
- Description: C1
- Description: 2003001830
An open problem : (4; g)-cages with odd g <= 5 are tightly connected
- Authors: Tang, Jianmin , Balbuena, Camino , Lin, Yuqing , Miller, Mirka
- Date: 2007
- Type: Text , Conference paper
- Relation: Paper presented at Thirteenth Computing : The Australasian Theory Symposium, CATS2007, Ballarat, Victoria : January 30th-Febuary 2nd p. 141-144
- Full Text: false
- Description: Interconnection networks form an important area which has received much attention, both in theoretical research and in practice. From theoretical point of view, an interconnection network can be modelled by a graph, where the vertices of the graph represent the nodes of the network and the edges of the graph represent connections between the nodes in the network. Fault tolerance is an important performance feature when designing a network, and the connectivity of the underlying graph is one of the measures of fault tolerance for a network. A graph is connected if there is a path between any two vertices of G. We say that G is t-connected if the deletion of at least t vertices of G is required to disconnect the graph. A graph with minimum degree delta is maximally connected if it is delta-connected. A graph is superconnected if its only minimum disconnecting sets are those induced by the neighbors of a vertex; a graph is said to be tightly superconnected if (i) any minimum disconnecting set is the set of neighbors of a single vertex; and (ii) the deletion of a minimum disconnecting set results in a graph with two components (one of which has only one vertex, another component is a connected graph). A (delta; g) - cage is a delta-regular graph with girth g and with the least possible number of vertices. In this paper we consider the problem of whether or not (4; g)-cages for g >= 5 are tightly superconnected. We present some partial results and the remaining open problems.
- Description: Interconnection networks form an important area which has received much attention, both in theoretical research and in practice. From theoretical point of view, an interconnection network can be modelled by a graph, where the vertices of the graph represent the nodes of the network and the edges of the graph represent connections between the nodes in the network. Fault tolerance is an important performance feature when designing a network, and the connectivity of the underlying graph is one of the measures of fault tolerance for a network. A graph is connected if there is a path between any two vertices of G. We say that G is t-connected if the deletion of at least t vertices of G is required to disconnect the graph. A graph with minimum degree \delta\ is maximally connected if it is \delta\-connected. A graph is superconnected if its only minimum disconnecting sets are those induced by the neighbors of a vertex; a graph is said to be tightly superconnected if (i) any minimum disconnecting set is the set of neighbors of a single vertex; and (ii) the deletion of a minimum disconnecting set results in a graph with two components (one of which has only one vertex, another component is a connected graph). A (\delta\; g) - cage is a \delta\-regular graph with girth g and with the least possible number of vertices. In this paper we consider the problem of whether or not (4; g)-cages for g >= 5 are tightly superconnected. We present some partial results and the remaining open problems.
- Description: 2003005018
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
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