Home  About us  Contact
 

Regular Graphs (regular + graph)

Distribution by Scientific Domains
Mathematics and Statistics100%

Terms modified by Regular Graphs

  • regular graph g
    		•

    Selected Abstracts

    d -Regular graphs of acyclic chromatic index at least d+2

    JOURNAL OF GRAPH THEORY, Issue 3 2010
    Manu Basavaraju
    Abstract An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and is denoted by a,(G). It was conjectured by Alon, Sudakov and Zaks (and earlier by Fiamcik) that a,(G),,+2, where ,=,(G) denotes the maximum degree of the graph. Alon et al. also raised the question whether the complete graphs of even order are the only regular graphs which require ,+2 colors to be acyclically edge colored. In this article, using a simple counting argument we observe not only that this is not true, but in fact all d -regular graphs with 2n vertices and d>n, requires at least d+ 2 colors. We also show that a,(Kn, n),n+ 2, when n is odd using a more non-trivial argument. (Here Kn, n denotes the complete bipartite graph with n vertices on each side.) This lower bound for Kn, n can be shown to be tight for some families of complete bipartite graphs and for small values of n. We also infer that for every d, n such that d,5, n,2d+ 3 and dn even, there exist d -regular graphs which require at least d+2-colors to be acyclically edge colored. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 226,230, 2010 [source]

    Regular graphs whose subgraphs tend to be acyclic

    RANDOM STRUCTURES AND ALGORITHMS, Issue 3 2006
    Noga Alon
    Motivated by a problem that arises in the study of mirrored storage systems, we describe, for any fixed ,, , > 0, and any integer d , 2, explicit or randomized constructions of d -regular graphs on n > n0(,, ,) vertices in which a random subgraph obtained by retaining each edge, randomly and independently, with probability , is acyclic with probability at least 1 , ,. On the other hand we show that for any d -regular graph G on n > n1(,, ,) vertices, a random subgraph of G obtained by retaining each edge, randomly and independently, with probability , does contain a cycle with probability at least 1 , ,. The proofs combine probabilistic and combinatorial arguments, with number theoretic techniques. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006 [source]

    The 2-dimensional rigidity of certain families of graphs

    JOURNAL OF GRAPH THEORY, Issue 2 2007
    Bill Jackson
    Abstract Laman's characterization of minimally rigid 2-dimensional generic frameworks gives a matroid structure on the edge set of the underlying graph, as was first pointed out and exploited by L. Lovász and Y. Yemini. Global rigidity has only recently been characterized by a combination of two results due to T. Jordán and the first named author, and R. Connelly, respectively. We use these characterizations to investigate how graph theoretic properties such as transitivity, connectivity and regularity influence (2-dimensional generic) rigidity and global rigidity and apply some of these results to reveal rigidity properties of random graphs. In particular, we characterize the globally rigid vertex transitive graphs, and show that a random d -regular graph is asymptotically almost surely globally rigid for all d , 4. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 154,166, 2007 [source]

    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]

    Circuits through prescribed vertices in k -connected k -regular graphs

    JOURNAL OF GRAPH THEORY, Issue 2 2002
    Roland Häggkvist
    Abstract We show that every set of vertices in a k -connected k -regular graph belongs to some circuit. © 2002 John Wiley & Sons, Inc. J Graph Theory 39: 145,163, 2002 [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]

    Minors in random regular graphs

    RANDOM STRUCTURES AND ALGORITHMS, Issue 4 2009
    Nikolaos Fountoulakis
    Abstract We show that there is a constant c so that for fixed r , 3 a.a.s. an r -regular graph on n vertices contains a complete graph on vertices as a minor. This confirms a conjecture of Markström (Ars Combinatoria 70 (2004) 289,295). Since any minor of an r -regular graph on n vertices has at most rn/2 edges, our bound is clearly best possible up to the value of the constant c. As a corollary, we also obtain the likely order of magnitude of the largest complete minor in a random graph Gn,p during the phase transition (i.e., when pn , 1). © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009 [source]

    Rainbow Hamilton cycles in random regular graphs

    RANDOM STRUCTURES AND ALGORITHMS, Issue 1-2 2007
    Svante Janson
    A rainbow subgraph of an edge-colored graph has all edges of distinct colors. A random d -regular graph with d even, and having edges colored randomly with d/2 of each of n colors, has a rainbow Hamilton cycle with probability tending to 1 as n ,,, for fixed d , 8. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2007 [source]

    Maximum weight independent sets and matchings in sparse random graphs.

    RANDOM STRUCTURES AND ALGORITHMS, Issue 1 2006
    Exact results using the local weak convergence method
    Let G(n,c/n) and Gr(n) be an n -node sparse random graph and a sparse random r -regular graph, respectively, and let I(n,r) and I(n,c) be the sizes of the largest independent set in G(n,c/n) and Gr(n). The asymptotic value of I(n,c)/n as n , ,, can be computed using the Karp-Sipser algorithm when c , e. For random cubic graphs, r = 3, it is only known that .432 , lim infnI(n,3)/n , lim supnI(n,3)/n , .4591 with high probability (w.h.p.) as n , ,, as shown in Frieze and Suen [Random Structures Algorithms 5 (1994), 649,664] and Bollabas [European J Combin 1 (1980), 311,316], respectively. In this paper we assume in addition that the nodes of the graph are equipped with nonnegative weights, independently generated according to some common distribution, and we consider instead the maximum weight of an independent set. Surprisingly, we discover that for certain weight distributions, the limit limnI(n,c)/n can be computed exactly even when c > e, and limnI(n,r)/n can be computed exactly for some r , 1. For example, when the weights are exponentially distributed with parameter 1, limnI(n,2e)/n , .5517, and limnI(n,3)/n , .6077. Our results are established using the recently developed local weak convergence method further reduced to a certain local optimality property exhibited by the models we consider. We extend our results to maximum weight matchings in G(n,c/n) and Gr(n). For the case of exponential distributions, we compute the corresponding limits for every c > 0 and every r , 2. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006 [source]

    On the asymmetry of random regular graphs and random graphs

    RANDOM STRUCTURES AND ALGORITHMS, Issue 3-4 2002
    Jeong Han Kim
    This paper studies the symmetry of random regular graphs and random graphs. Our main result shows that for all 3 , d , n , 4 the random d -regular graph on n vertices almost surely has no nontrivial automorphisms. This answers an open question of N. Wormald [13]. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 21: 216,224, 2002 [source]

    d -Regular graphs of acyclic chromatic index at least d+2

    JOURNAL OF GRAPH THEORY, Issue 3 2010
    Manu Basavaraju
    Abstract An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and is denoted by a,(G). It was conjectured by Alon, Sudakov and Zaks (and earlier by Fiamcik) that a,(G),,+2, where ,=,(G) denotes the maximum degree of the graph. Alon et al. also raised the question whether the complete graphs of even order are the only regular graphs which require ,+2 colors to be acyclically edge colored. In this article, using a simple counting argument we observe not only that this is not true, but in fact all d -regular graphs with 2n vertices and d>n, requires at least d+ 2 colors. We also show that a,(Kn, n),n+ 2, when n is odd using a more non-trivial argument. (Here Kn, n denotes the complete bipartite graph with n vertices on each side.) This lower bound for Kn, n can be shown to be tight for some families of complete bipartite graphs and for small values of n. We also infer that for every d, n such that d,5, n,2d+ 3 and dn even, there exist d -regular graphs which require at least d+2-colors to be acyclically edge colored. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 226,230, 2010 [source]

    Maximum acyclic and fragmented sets in regular graphs

    JOURNAL OF GRAPH THEORY, Issue 2 2008
    Penny Haxell
    Abstract We show that a typical d -regular graph G of order n does not contain an induced forest with around vertices, when n,,,d,,,1, this bound being best possible because of a result of Frieze and ,uczak [6]. We then deduce an affirmative answer to an open question of Edwards and Farr (see [4]) about fragmentability, which concerns large subgraphs with components of bounded size. An alternative, direct answer to the question is also given. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 149,156, 2008 [source]

    Circuits through prescribed vertices in k -connected k -regular graphs

    JOURNAL OF GRAPH THEORY, Issue 2 2002
    Roland Häggkvist
    Abstract We show that every set of vertices in a k -connected k -regular graph belongs to some circuit. © 2002 John Wiley & Sons, Inc. J Graph Theory 39: 145,163, 2002 [source]

    A family of graphs and the degree/diameter problem

    JOURNAL OF GRAPH THEORY, Issue 2 2001
    Geoffrey Exoo
    Abstract We investigate a family of graphs relevant to the problem of finding large regular graphs with specified degree and diameter. Our family contains the largest known graphs for degree/diameter pairs (3, 7), (3, 8), (4, 4), (5, 3), (5, 5), (6, 3), (6, 4), (7, 3), (14, 3), and (16, 2). We also find a new bound for (3, 6) by an unrelated method. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 118,124, 2001 [source]

    Super edge- and point-connectivities of the Cartesian product of regular graphs

    NETWORKS: AN INTERNATIONAL JOURNAL, Issue 2 2002
    Bih-Sheue Shieh
    Abstract We prove that the Cartesian product of two regular graphs with maximum edge (respectively, point-)-connectivity is super edge (respectively, point-)-connected except for the case K2 × Kn, n , 2 (respectively, n , 4), where Kn is a complete graph of order n. Using these results, certain classes of networks which are recursively defined by the Cartesian product can be simply shown to possess super edge-connectivity and super point-connectivity. © 2002 Wiley Periodicals, Inc. [source]

    Minors in random regular graphs

    RANDOM STRUCTURES AND ALGORITHMS, Issue 4 2009
    Nikolaos Fountoulakis
    Abstract We show that there is a constant c so that for fixed r , 3 a.a.s. an r -regular graph on n vertices contains a complete graph on vertices as a minor. This confirms a conjecture of Markström (Ars Combinatoria 70 (2004) 289,295). Since any minor of an r -regular graph on n vertices has at most rn/2 edges, our bound is clearly best possible up to the value of the constant c. As a corollary, we also obtain the likely order of magnitude of the largest complete minor in a random graph Gn,p during the phase transition (i.e., when pn , 1). © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009 [source]

    Short cycle distribution in random regular graphs recursively generated by pegging

    RANDOM STRUCTURES AND ALGORITHMS, Issue 1 2009
    Pu Gao
    Abstract We introduce a new method of generating random d -regular graphs by repeatedly applying an operation called pegging. The pegging operation is abstracted from a type of basic operation applied in a type of peer-to-peer network called the SWAN network. We prove that for the resulting graphs, the limiting joint distribution of the numbers of short cycles is independent Poisson. We also use coupling to bound the rate at which the distribution approaches its limit. The coupling involves two different, though quite similar, Markov chains that are not time-homogeneous. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2009 [source]

    Rainbow Hamilton cycles in random regular graphs

    RANDOM STRUCTURES AND ALGORITHMS, Issue 1-2 2007
    Svante Janson
    A rainbow subgraph of an edge-colored graph has all edges of distinct colors. A random d -regular graph with d even, and having edges colored randomly with d/2 of each of n colors, has a rainbow Hamilton cycle with probability tending to 1 as n ,,, for fixed d , 8. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2007 [source]

    Regular graphs whose subgraphs tend to be acyclic

    RANDOM STRUCTURES AND ALGORITHMS, Issue 3 2006
    Noga Alon
    Motivated by a problem that arises in the study of mirrored storage systems, we describe, for any fixed ,, , > 0, and any integer d , 2, explicit or randomized constructions of d -regular graphs on n > n0(,, ,) vertices in which a random subgraph obtained by retaining each edge, randomly and independently, with probability , is acyclic with probability at least 1 , ,. On the other hand we show that for any d -regular graph G on n > n1(,, ,) vertices, a random subgraph of G obtained by retaining each edge, randomly and independently, with probability , does contain a cycle with probability at least 1 , ,. The proofs combine probabilistic and combinatorial arguments, with number theoretic techniques. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006 [source]

    On the asymmetry of random regular graphs and random graphs

    RANDOM STRUCTURES AND ALGORITHMS, Issue 3-4 2002
    Jeong Han Kim
    This paper studies the symmetry of random regular graphs and random graphs. Our main result shows that for all 3 , d , n , 4 the random d -regular graph on n vertices almost surely has no nontrivial automorphisms. This answers an open question of N. Wormald [13]. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 21: 216,224, 2002 [source]

    Hamilton cycles containing randomly selected edges in random regular graphs

    RANDOM STRUCTURES AND ALGORITHMS, Issue 2 2001
    R.W. Robinson
    In previous papers the authors showed that almost all d -regular graphs for d,3 are hamiltonian. In the present paper this result is generalized so that a set of j oriented root edges have been randomly specified for the cycle to contain. The Hamilton cycle must be orientable to agree with all of the orientations on the j root edges. It is shown that the requisite Hamilton cycle almost surely exists if and the limiting probability distribution at the threshold is determined when d=3. It is a corollary (in view of results elsewhere) that almost all claw-free cubic graphs are hamiltonian. There is a variation in which an additional cyclic ordering on the root edges is imposed which must also agree with their ordering on the Hamilton cycle. In this case, the required Hamilton cycle almost surely exists if j=o(n2/5). The method of analysis is small subgraph conditioning. This gives results on contiguity and the distribution of the number of Hamilton cycles which imply the facts above. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 19: 128,147, 2001 [source]