Subgraph

Distribution by Scientific Domains

Kinds of Subgraph

  • induced subgraph
  • spanning subgraph


  • Selected Abstracts


    What makes biochemical networks tick?

    FEBS JOURNAL, Issue 19 2004
    A graphical tool for the identification of oscillophores
    In view of the increasing number of reported concentration oscillations in living cells, methods are needed that can identify the causes of these oscillations. These causes always derive from the influences that concentrations have on reaction rates. The influences reach over many molecular reaction steps and are defined by the detailed molecular topology of the network. So-called ,autoinfluence paths', which quantify the influence of one molecular species upon itself through a particular path through the network, can have positive or negative values. The former bring a tendency towards instability. In this molecular context a new graphical approach is presented that enables the classification of network topologies into oscillophoretic and nonoscillophoretic, i.e. into ones that can and ones that cannot induce concentration oscillations. The network topologies are formulated in terms of a set of uni-molecular and bi-molecular reactions, organized into branched cycles of directed reactions, and presented as graphs. Subgraphs of the network topologies are then classified as negative ones (which can) and positive ones (which cannot) give rise to oscillations. A subgraph is oscillophoretic (negative) when it contains more positive than negative autoinfluence paths. Whether the former generates oscillations depends on the values of the other subgraphs, which again depend on the kinetic parameters. An example shows how this can be established. By following the rules of our new approach, various oscillatory kinetic models can be constructed and analyzed, starting from the classified simplest topologies and then working towards desirable complications. Realistic biochemical examples are analyzed with the new method, illustrating two new main classes of oscillophore topologies. [source]


    The Probabilistic Minimum Vertex-covering Problem

    INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, Issue 1 2002
    Cécile Murat
    An instance of the probabilistic vertex-covering problem is a pair (G=(V,E),Pr) obtained by associating with each vertex ,i,V an ,occurrence' probability pi. We consider a modification strategy , transforming a vertex cover C for G into a vertex cover CI for the subgraph of G induced by a vertex-set I,V. The objective for the probabilistic vertex-covering is to determine a vertex cover of G minimizing the sum, over all subsets I,V, of the products: probability of I times CI. In this paper, we study the complexity of optimally solving probabilistic vertex-covering. [source]


    Subgraph-avoiding coloring of graphs

    JOURNAL OF GRAPH THEORY, Issue 4 2010
    Jia Shen
    Abstract Given a "forbidden graph" F and an integer k, an F-avoiding k-coloring of a graph G is a k -coloring of the vertices of G such that no maximal F -free subgraph of G is monochromatic. The F-avoiding chromatic numberacF(G) is the smallest integer k such that G is F -avoiding k -colorable. In this paper, we will give a complete answer to the following question: for which graph F, does there exist a constant C, depending only on F, such that acF(G) , C for any graph G? For those graphs F with unbounded avoiding chromatic number, upper bounds for acF(G) in terms of various invariants of G are also given. Particularly, we prove that , where n is the order of G and F is not Kk or . © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 300,310, 2010 [source]


    A structure theorem for graphs with no cycle with a unique chord and its consequences

    JOURNAL OF GRAPH THEORY, Issue 1 2010
    Nicolas Trotignon
    Abstract We give a structural description of the class ,, of graphs that do not contain a cycle with a unique chord as an induced subgraph. Our main theorem states that any connected graph in ,, is either in some simple basic class or has a decomposition. Basic classes are chordless cycles, cliques, bipartite graphs with one side containing only nodes of degree 2 and induced subgraphs of the famous Heawood or Petersen graph. Decompositions are node cutsets consisting of one or two nodes and edge cutsets called 1-joins. Our decomposition theorem actually gives a complete structure theorem for ,,, i.e. every graph in ,, can be built from basic graphs that can be explicitly constructed, and gluing them together by prescribed composition operations, and all graphs built this way are in ,,. This has several consequences: an ,,(nm) -time algorithm to decide whether a graph is in ,,, an ,,(n+ m) -time algorithm that finds a maximum clique of any graph in ,,, and an ,,(nm) -time coloring algorithm for graphs in ,,. We prove that every graph in ,, is either 3-colorable or has a coloring with , colors where , is the size of a largest clique. The problem of finding a maximum stable set for a graph in ,, is known to be NP-hard. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 31,67, 2010 [source]


    K6 -minors in triangulations and complete quadrangulations

    JOURNAL OF GRAPH THEORY, Issue 4 2009
    Raiji Mukae
    Abstract In this paper, we shall prove that a projective-planar (resp., toroidal) triangulation G has K6 as a minor if and only if G has no quadrangulation isomorphic to K4 (resp., K5 ) as a subgraph. As an application of the theorems, we can prove that Hadwiger's conjecture is true for projective-planar and toroidal triangulations. © 2009 Wiley Periodicals, Inc. J Graph Theory 60: 302-312, 2009 [source]


    On conjectures of Frankl and El-Zahar

    JOURNAL OF GRAPH THEORY, Issue 4 2008
    Bernardo Llano
    Abstract An induced subgraph of a graph is called a derived subgraph of if contains no isolated vertices. An edge e of is said to be residual if e occurs in more than half of the derived subgraphs of . In this article, we prove that every simple graph with at least one edge contains a non-residual edge. This was conjectured by El-Zahar in 1997. © 2008 Wiley Periodicals, Inc. J Graph Theory 57: 344,352, 2008 [source]


    Graph classes characterized both by forbidden subgraphs and degree sequences

    JOURNAL OF GRAPH THEORY, Issue 2 2008
    Michael D. Barrus
    Abstract Given a set of graphs, a graph G is -free if G does not contain any member of as an induced subgraph. We say that is a degree-sequence-forcing set if, for each graph G in the class of -free graphs, every realization of the degree sequence of G is also in . We give a complete characterization of the degree-sequence-forcing sets when has cardinality at most two. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 131,148, 2008 [source]


    On k -detour subgraphs of hypercubes

    JOURNAL OF GRAPH THEORY, Issue 1 2008
    Nana Arizumi
    Abstract A spanning subgraph G of a graph H is a k - detour subgraph of H if for each pair of vertices , the distance, , between x and y in G exceeds that in H by at most k. Such subgraphs sometimes also are called additive spanners. In this article, we study k -detour subgraphs of the n -dimensional cube, , with few edges or with moderate maximum degree. Let denote the minimum possible maximum degree of a k -detour subgraph of . The main result is that for every and On the other hand, for each fixed even and large n, there exists a k -detour subgraph of with average degree at most . © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 55,64, 2008 [source]


    Forcing highly connected subgraphs

    JOURNAL OF GRAPH THEORY, Issue 4 2007
    Maya Jakobine Stein
    Abstract A theorem of Mader states that highly connected subgraphs can be forced in finite graphs by assuming a high minimum degree. We extend this result to infinite graphs. Here, it is necessary to require not only high degree for the vertices but also high vertex-degree (or multiplicity) for the ends of the graph, that is, a large number of disjoint rays in each end. We give a lower bound on the degree of vertices and the vertex-degree of the ends which is quadratic in k, the connectedness of the desired subgraph. In fact, this is not far from best possible: we exhibit a family of graphs with a degree of order 2k at the vertices and a vertex-degree of order k log k at the ends which have no k -connected subgraphs. Furthermore, if in addition to the high degrees at the vertices, we only require high edge-degree for the ends (which is defined as the maximum number of edge-disjoint rays in an end), Mader's theorem does not extend to infinite graphs, not even to locally finite ones. We give a counterexample in this respect. But, assuming a lower bound of at least 2k for the edge-degree at the ends and the degree at the vertices does suffice to ensure the existence (k + 1)- edge -connected subgraphs in arbitrary graphs. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 331,349, 2007 [source]


    The last excluded case of Dirac's map-color theorem for choosability

    JOURNAL OF GRAPH THEORY, Issue 4 2006
    Daniel Král'
    Abstract In 1890, Heawood established the upper bound on the chromatic number of every graph embedded on a surface of Euler genus , , 1. Almost 80 years later, the bound was shown to be tight by Ringel and Youngs. These two results have became known under the name of the Map-Color Theorem. In 1956, Dirac refined this by showing that the upper bound H(,) is obtained only if a graph G contains KH, as a subgraph except for three surfaces. Albertson and Hutchinson settled these excluded cases in 1979. This result is nowadays known as Dirac's Map-Color Theorem. Böhme, Mohar, and Stiebitz extended Dirac's Map-Color Theorem to the case of choosability by showing that G is (H(,) , 1)-choosable unless G contains KH(,) as a subgraph for , , 1 and , , 3. In the present paper, we settle the excluded case of , = 3. © 2005 Wiley Periodicals, Inc. J Graph Theory 51: 319,354, 2006 [source]


    On two Turán Numbers

    JOURNAL OF GRAPH THEORY, Issue 3 2006
    Jian Shen
    Abstract Let H(3,1) denote the complete bipartite graph K3,3 with an edge deleted. For given graphs G and F, the Turán numbers (G, F) denote the maximum number of edges in a subgraph of G containing no copy of F. We prove that ) and that , which improve earlier results of Mubayi-West [13] and Füredi-West [10], respectively. The generalized Ramsey parameter r(G, F, q) denotes the minimum number of colors needed to edge-color G such that every copy of F in G receives at least q colors. As an immediate consequence, the above results imply that and that , respectively. These improve the corresponding bounds given by Mubayi [12] recently. © 2005 Wiley Periodicals [source]


    Disjoint clique cutsets in graphs without long holes

    JOURNAL OF GRAPH THEORY, Issue 4 2005
    Elaine M. Eschen
    Abstract A biclique cutset is a cutset that induces the disjoint union of two cliques. A hole is an induced cycle with at least five vertices. A graph is biclique separable if it has no holes and each induced subgraph that is not a clique contains a clique cutset or a biclique cutset. The class of biclique separable graphs contains several well-studied graph classes, including triangulated graphs. We prove that for the class of biclique separable graphs, the recognition problem, the vertex coloring problem, and the clique problem can be solved efficiently. Our algorithms also yield a proof that biclique separable graphs are perfect. Our coloring algorithm is actually more general and can be applied to graphs that can be decomposed via a special type of biclique cutset. Our algorithms are based on structural results on biclique separable graphs developed in this paper. © 2005 Wiley Periodicals, Inc. J Graph Theory 48: 277,298, 2005 [source]


    Toughness, minimum degree, and spanning cubic subgraphs

    JOURNAL OF GRAPH THEORY, Issue 2 2004
    D. Bauer
    Abstract Degree conditions on the vertices of a t -tough graph G (1,,,t,<,3) are presented which ensure the existence of a spanning cubic subgraph in G. These conditions are best possible to within a small additive constant for every fixed rational t ,[1,4/3),[2,8/3). © 2003 Wiley Periodicals, Inc. J Graph Theory 45: 119,141, 2004 [source]


    Nowhere-zero 3-flows in locally connected graphs

    JOURNAL OF GRAPH THEORY, Issue 3 2003
    Hong-Jian Lai
    Abstract Let G be a graph. For each vertex v ,V(G), Nv denotes the subgraph induces by the vertices adjacent to v in G. The graph G is locally k -edge-connected if for each vertex v ,V(G), Nv is k -edge-connected. In this paper we study the existence of nowhere-zero 3-flows in locally k -edge-connected graphs. In particular, we show that every 2-edge-connected, locally 3-edge-connected graph admits a nowhere-zero 3-flow. This result is best possible in the sense that there exists an infinite family of 2-edge-connected, locally 2-edge-connected graphs each of which does not have a 3-NZF. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 211,219, 2003 [source]


    Connected (g, f)-factors

    JOURNAL OF GRAPH THEORY, Issue 1 2002
    M. N. Ellingham
    Abstract In this paper we study connected (g, f)-factors. We describe an algorithm to connect together an arbitrary spanning subgraph of a graph, without increasing the vertex degrees too much; if the algorithm fails we obtain information regarding the structure of the graph. As a consequence we give sufficient conditions for a graph to have a connected (g, f)-factor, in terms of the number of components obtained when we delete a set of vertices. As corollaries we can derive results of Win [S. Win, Graphs Combin 5 (1989), 201,205], Xu et al. [B. Xu, Z. Liu, and T. Tokuda, Graphs Combin 14 (1998), 393,395] and Ellingham and Zha [M. N. Ellingham and Xiaoya Zha, J Graph Theory 33 (2000), 125,137]. We show that a graph has a connected [a, b]-factor (b>a,,,2) if the graph is tough enough; when b,,,a,+,2, toughness at least suffices. We also show that highly edge-connected graphs have spanning trees of relatively low degree; in particular, an m -edge-connected graph G has a spanning tree T such that degT (,),,,2,+,, degG(,)/m, for each vertex ,. © 2002 John Wiley & Sons, Inc. J Graph Theory 39: 62,75, 2002 [source]


    On factors of 4-connected claw-free graphs,

    JOURNAL OF GRAPH THEORY, Issue 2 2001
    H. J. Broersma
    Abstract We consider the existence of several different kinds of factors in 4-connected claw-free graphs. This is motivated by the following two conjectures which are in fact equivalent by a recent result of the third author. Conjecture 1 (Thomassen): Every 4-connected line graph is hamiltonian, i.e., has a connected 2-factor. Conjecture 2 (Matthews and Sumner): Every 4-connected claw-free graph is hamiltonian. We first show that Conjecture 2 is true within the class of hourglass-free graphs, i.e., graphs that do not contain an induced subgraph isomorphic to two triangles meeting in exactly one vertex. Next we show that a weaker form of Conjecture 2 is true, in which the conclusion is replaced by the conclusion that there exists a connected spanning subgraph in which each vertex has degree two or four. Finally we show that Conjectures 1 and 2 are equivalent to seemingly weaker conjectures in which the conclusion is replaced by the conclusion that there exists a spanning subgraph consisting of a bounded number of paths © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 125,136, 2001 [source]


    Measuring beta-diversity from taxonomic similarity

    JOURNAL OF VEGETATION SCIENCE, Issue 6 2007
    Giovanni Bacaro
    Abstract Question: The utility of beta (,-) diversity measures that incorporate information about the degree of taxonomic (dis)similarity between species plots is becoming increasingly recognized. In this framework, the question for this study is: can we define an ecologically meaningful index of ,-diversity that, besides indicating simple species turnover, is able to account for taxonomic similarity amongst species in plots? Methods: First, the properties of existing measures of taxonomic similarity measures are briefly reviewed. Next, a new measure of plot-to-plot taxonomic similarity is presented that is based on the maximal common subgraph of two taxonomic trees. The proposed measure is computed from species presences and absences and include information about the degree of higher-level taxonomic similarity between species plots. The performance of the proposed measure with respect to existing coefficients of taxonomic similarity and the coefficient of Jaccard is discussed using a small data set of heath plant communities. Finally, a method to quantify ,-diversity from taxonomic dissimilarities is discussed. Results: The proposed measure of taxonomic ,-diversity incorporates not only species richness, but also information about the degree of higher-order taxonomic structure between species plots. In this view, it comes closer to a modern notion of biological diversity than more traditional measures of ,-di-versity. From regression analysis between the new coefficient and existing measures of taxonomic similarity it is shown that there is an evident nonlinearity between the coefficients. This nonlinearity demonstrates that the new coefficient measures similarity in a conceptually different way from previous indices. Also, in good agreement with the findings of previous authors, the regression between the new index and the Jaccard coefficient of similarity shows that more than 80% of the variance of the former is explained by the community structure at the species level, while only the residual variance is explained by differences in the higher-order taxonomic structure of the species plots. This means that a genuine taxonomic approach to the quantification of plot-to-plot similarity is only needed if we are interested in the residual system's variation that is related to the higher-order taxonomic structure of a pair of species plots. [source]


    A generalization of an edge-connectivity theorem of Chartrand

    NETWORKS: AN INTERNATIONAL JOURNAL, Issue 2 2009
    Frank Boesch
    Abstract In 1966, Chartrand proved that if the minimum degree of a graph is at least the floor of half the number of nodes, then its edge-connectivity equals its minimum degree. A more discriminating notion of edge-connectivity is introduced, called the k -component order edge-connectivity, which is the minimum number of edges required to be removed so that the order of each component of the resulting subgraph is less than k. Results are established that guarantee that this parameter is at least as large as the minimum degree, provided the minimum degree is sufficiently large. This generalizes Chartrand's result. It is also determined when these results are best possible. © 2009 Wiley Periodicals, Inc. NETWORKS, 2009 [source]


    Approximability of unsplittable shortest path routing problems,

    NETWORKS: AN INTERNATIONAL JOURNAL, Issue 1 2009
    Andreas Bley
    Abstract In this article, we discuss the relation of unsplittable shortest path routing (USPR) to other routing schemes and study the approximability of three USPR network planning problems. Given a digraph D = (V,A) and a set K of directed commodities, an USPR is a set of flow paths P, (s,t) , K, such that there exists a metric , = (,a) , Z with respect to which each P is the unique shortest (s,t)-path. In the Min-Con-USPR problem, we seek an USPR that minimizes the maximum congestion over all arcs. We show that this problem is NP-hard to approximate within a factor of O(|V|1,,), but polynomially approximable within min(|A|,|K|) in general and within O(1) if the underlying graph is an undirected cycle or a bidirected ring. We also construct examples where the minimum congestion that can be obtained by USPR is a factor of ,(|V|2) larger than that achievable by unsplittable flow routing or by shortest multipath routing, and a factor of ,(|V|) larger than that achievable by unsplittable source-invariant routing. In the CAP -USPR problem, we seek a minimum cost installation of integer arc capacities that admit an USPR of the given commodities. We prove that this problem is NP-hard to approximate within 2 , , even in the undirected case, and we devise approximation algorithms for various special cases. The fixed charge network design problem FC-USPR, where the task is to find a minimum cost subgraph of D whose fixed arc capacities admit an USPR of the commodities, is shown to be NPO-complete. All three problems are of great practical interest in the planning of telecommunication networks that are based on shortest path routing protocols. Our results indicate that they are harder than the corresponding unsplittable flow or shortest multi-path routing problems. © 2009 Wiley Periodicals, Inc. NETWORKS, 2009 [source]


    Approximating the smallest k -edge connected spanning subgraph by LP-rounding

    NETWORKS: AN INTERNATIONAL JOURNAL, Issue 4 2009
    Harold N. Gabow
    Abstract The smallest k-ECSS problem is, given a graph along with an integer k, find a spanning subgraph that is k -edge connected and contains the fewest possible number of edges. We examine a natural approximation algorithm based on rounding an LP solution. A tight bound on the approximation ratio is 1 + 3/k for undirected graphs with k > 1 odd, 1 + 2/k for undirected graphs with k even, and 1 + 2/k for directed graphs with k arbitrary. Using iterated rounding improves the first upper bound to 1 + 2/k. On the hardness side we show that for some absolute constant c > 0, for any integer k , 2 (k , 1), a polynomial-time algorithm approximating the smallest k -ECSS on undirected (directed) multigraphs to within ratio 1 + c/k would imply P = NP. © 2008 Wiley Periodicals, Inc. NETWORKS, 2009 [source]


    Approximation algorithm for the group Steiner network problem

    NETWORKS: AN INTERNATIONAL JOURNAL, Issue 2 2007
    Michal Penn
    Abstract In this article we study the group Steiner network problem, which is defined in the following way. Given a graph G = (V,E), a partition of its vertices into K groups and connectivity requirements between the different groups, the aim is to find simultaneously a set of representatives, one for each group, and a minimum cost connected subgraph that satisfies the connectivity requirements between the groups (representatives). This problem is a generalization of the Steiner network problem and the group Steiner tree problem, two known NP-complete problems. We present an approximation algorithm for a special case of the group Steiner network problem with an approximation ratio of min {2(1 + 2x),2I}, where I is the cardinality of the largest group and x is a parameter that depends on the cost function. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 49(2), 160,167 2007 [source]


    The strongly connected reliability of complete digraphs

    NETWORKS: AN INTERNATIONAL JOURNAL, Issue 3 2005
    J.I. Brown
    Abstract Given a digraph D, consider the model where each vertex is always operational, but the edges are independently operational with probability p. The strongly connected reliability of D, scRel(D,p), is the probability that the spanning subgraph of D consisting of the operational edges is strongly connected. One can view strongly connected reliability as the probability that any vertex can send information to any other vertex, given that edges fail independently. There are very few classes for which there is an efficient algorithm for calculating the strongly connected reliability. This article presents the fist polynomial time algorithm for computing the strongly connected reliability of complete digraphs, that is, digraphs in which every vertex is joined to every other vertex by exactly one edge (one in each direction). © 2005 Wiley Periodicals, Inc. NETWORKS, Vol. 45(3), 165,168 2005 [source]


    Approximation algorithms for finding low-degree subgraphs

    NETWORKS: AN INTERNATIONAL JOURNAL, Issue 3 2004
    Philip N. Klein
    Abstract We give quasipolynomial-time approximation algorithms for designing networks with a minimum degree. Using our methods, one can design networks whose connectivity is specified by "proper" functions, a class of 0,1 functions indicating the number of edges crossing each cut. We also provide quasipolynomial-time approximation algorithms for finding two-edge-connected spanning subgraphs of approximately minimum degree of a given two-edge-connected graph, and a spanning tree (branching) of approximately minimum degree of a directed graph. The degree of the output network in all cases is guaranteed to be at most (1 + ,) times the optimal degree, plus an additive O(log1+,n) for any , > 0. Our analysis indicates that the degree of an optimal subgraph for each of the problems above is well estimated by certain polynomially solvable linear programs. This suggests that the linear programs we describe could be useful in obtaining optimal solutions via branch and bound. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 44(3), 203,215 2004 [source]


    The 2-path network problem

    NETWORKS: AN INTERNATIONAL JOURNAL, Issue 3 2004
    Geir Dahl
    Abstract Given a graph with nonnegative edge weights and a set D of node pairs, the 2- path network problem requires a minimum weight set of edges such that the induced subgraph contains a path with one or two edges connecting each pair in D. The problem is NP -hard. We present two integer programming models for the problem and study properties of associated polytopes, including cutting planes. Two approximation algorithms are suggested and analyzed. Some computational experience is reported. © 2004 Wiley Periodicals, Inc. [source]


    On the power of BFS to determine a graph's diameter,

    NETWORKS: AN INTERNATIONAL JOURNAL, Issue 4 2003
    Derek G. Corneil
    Abstract Recently, considerable effort has been spent on showing that Lexicographic Breadth First Search (LBFS) can be used to determine a tight bound on the diameter of graphs from various restricted classes. In this paper, we show that, in some cases, the full power of LBFS is not required and that other variations of Breadth First Search (BFS) suffice. The restricted graph classes that are amenable to this approach all have a small constant upper bound on the maximum-sized cycle that may appear as an induced subgraph. We show that, on graphs that have no induced cycle of size greater than k, BFS finds an estimate of the diameter that is no worse than diam(G) , ,k/2,. © 2003 Wiley Periodicals, Inc. [source]


    The clique partitioning problem: Facets and patching facets

    NETWORKS: AN INTERNATIONAL JOURNAL, Issue 4 2001
    Maarten Oosten
    Abstract The clique partitioning problem (CPP) can be formulated as follows: Given is a complete graph G = (V, E), with edge weights wij , , for all {i, j} , E. A subset A , E is called a clique partition if there is a partition of V into nonempty, disjoint sets V1,,, Vk, such that each Vp (p = 1,,, k) induces a clique (i.e., a complete subgraph), and A = , {{i, j}|i, j , Vp, i , j}. The weight of such a clique partition A is defined as ,{i,j},Awij. The problem is now to find a clique partition of maximum weight. The clique partitioning polytope P is the convex hull of the incidence vectors of all clique partitions of G. In this paper, we introduce several new classes of facet-defining inequalities of P. These suffice to characterize all facet-defining inequalities with right-hand side 1 or 2. Also, we present a procedure, called patching, which is able to construct new facets by making use of already-known facet-defining inequalities. A variant of this procedure is shown to run in polynomial time. Finally, we give limited empirical evidence that the facet-defining inequalities presented here can be of use in a cutting-plane approach for the clique partitioning problem. © 2001 John Wiley & Sons, Inc. [source]


    Random dense bipartite graphs and directed graphs with specified degrees

    RANDOM STRUCTURES AND ALGORITHMS, Issue 2 2009
    Catherine Greenhill
    Abstract Let s and t be vectors of positive integers with the same sum. We study the uniform distribution on the space of simple bipartite graphs with degree sequence s in one part and t in the other; equivalently, binary matrices with row sums s and column sums t. In particular, we find precise formulae for the probabilities that a given bipartite graph is edge-disjoint from, a subgraph of, or an induced subgraph of a random graph in the class. We also give similar formulae for the uniform distribution on the set of simple directed graphs with out-degrees s and in-degrees t. In each case, the graphs or digraphs are required to be sufficiently dense, with the degrees varying within certain limits, and the subgraphs are required to be sufficiently sparse. Previous results were restricted to spaces of sparse graphs. Our theorems are based on an enumeration of bipartite graphs avoiding a given set of edges, proved by multidimensional complex integration. As a sample application, we determine the expected permanent of a random binary matrix with row sums s and column sums t. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009 [source]


    A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs,

    RANDOM STRUCTURES AND ALGORITHMS, Issue 4 2007
    Surender Baswana
    Abstract Let G = (V,E) be an undirected weighted graph on |V | = n vertices and |E| = m edges. A t -spanner of the graph G, for any t , 1, is a subgraph (V,ES), ES , E, such that the distance between any pair of vertices in the subgraph is at most t times the distance between them in the graph G. Computing a t -spanner of minimum size (number of edges) has been a widely studied and well-motivated problem in computer science. In this paper we present the first linear time randomized algorithm that computes a t -spanner of a given weighted graph. Moreover, the size of the t -spanner computed essentially matches the worst case lower bound implied by a 43-year old girth lower bound conjecture made independently by Erd,s, Bollobás, and Bondy & Simonovits. Our algorithm uses a novel clustering approach that avoids any distance computation altogether. This feature is somewhat surprising since all the previously existing algorithms employ computation of some sort of local or global distance information, which involves growing either breadth first search trees up to ,(t)-levels or full shortest path trees on a large fraction of vertices. The truly local approach of our algorithm also leads to equally simple and efficient algorithms for computing spanners in other important computational environments like distributed, parallel, and external memory. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2007 [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]