Girth G (girth + g)

Distribution by Scientific Domains


Selected Abstracts


All (k;g)-cages are k -edge-connected

JOURNAL OF GRAPH THEORY, Issue 3 2005
Yuqing Lin
Abstract A (k;g)-cage is a k -regular graph with girth g and with the least possible number of vertices. In this paper, we prove that (k;g)-cages are k -edge-connected if g is even. Earlier, Wang, Xu, and Wang proved that (k;g)-cages are k -edge-connected if g is odd. Combining our results, we conclude that the (k;g)-cages are k -edge-connected. © 2005 Wiley Periodicals, Inc. J Graph Theory 48: 219,227, 2005 [source]


All (k;g)-cages are edge-superconnected

NETWORKS: AN INTERNATIONAL JOURNAL, Issue 2 2006
Yuqing Lin
Abstract A (k;g)-cage is a 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. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 47(2), 102,110 2006 [source]


Edge-superconnectivity of cages

NETWORKS: AN INTERNATIONAL JOURNAL, Issue 1 2004
X. Marcote
Abstract A graph with minimum degree , is said to be edge-superconnected if each minimum edge-cut consists of all the edges incident with some vertex (so , = ,). A smallest ,-regular graph G with girth g is said to be a (,, g)-cage. We show that every (,, g)-cage with odd girth is edge-superconnected. This result strengthens one obtained by Wang et al. (, = , for every such cage) and supports the conjecture of Fu et al. that all (,, g)-cages are ,-connected. © 2003 Wiley Periodicals, Inc. [source]


Randomly coloring graphs with lower bounds on girth and maximum degree

RANDOM STRUCTURES AND ALGORITHMS, Issue 2 2003
Martin Dyer
We consider the problem of generating a random q -coloring of a graph G = (V, E). We consider the simple Glauber Dynamics chain. We show that if the maximum degree , > c1ln n and the girth g > c2ln , (n = |V|) for sufficiently large c1, c2, then this chain mixes rapidly provided q/, > ,, where , , 1.763 is the root of , = e1/,. For this class of graphs, this beats the 11,/6 bound of Vigoda E. Vigoda, Improved bounds for sampling colorings, Proc 40th Annu IEEE Symp Foundations of Computer Science, 1999, pp. 51,59 for general graphs. We extend the result to random graphs. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 23: 167,179, 2003 [source]