Home  About us  Contact
 

Edge Set (edge + set)

Distribution by Scientific Domains
Mathematics and Statistics100%

Selected Abstracts

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]

An algebraic characterization of projective-planar graphs

JOURNAL OF GRAPH THEORY, Issue 4 2003
Lowell Abrams
Abstract We give a detailed algebraic characterization of when a graph G can be imbedded in the projective plane. The characterization is in terms of the existence of a dual graph G* on the same edge set as G, which satisfies algebraic conditions inspired by homology groups and intersection products in homology groups. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 320,331, 2003 [source]

On d -threshold graphs and d -dimensional bin packing

NETWORKS: AN INTERNATIONAL JOURNAL, Issue 4 2004
Alberto Caprara
Abstract We illustrate efficient algorithms to find a maximum stable set and a maximum matching in a graph with n nodes given by the edge union of d threshold graphs on the same node set, in case the d graphs in the union are known. Actually, because the edge set of a threshold graph can be implicitly represented by assigning values to the nodes, we assume that we know these values for each of the d graphs in the union. We present an O(n log n + nd,1) time algorithm to find a maximum stable set and an O(n2) time algorithm to find a maximum matching, in case d is constant. For the case d = 2, the running time of the latter is reduced to O(n log n) provided an additional technical condition is satisfied. The natural application of our results is the fast computation of lower bounds for the d -dimensional bin packing problem, for which the compatibility relations between items are represented by the edge union of d threshold graphs with one node for each item, the value of the node for the i -th graph being equal to the size of the item on the i -th dimension. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 44(4), 266,280 2004 [source]

Avoiding a giant component

RANDOM STRUCTURES AND ALGORITHMS, Issue 1 2001
Tom Bohman
Let e1,,e,1; e2,,e,2;,;ei,,e,i;,,, be a sequence of ordered pairs of edges chosen uniformly at random from the edge set of the complete graph Kn (i.e. we sample with replacement). This sequence is used to form a graph by choosing at stage i, i=1,,, one edge from ei,e,i to be an edge in the graph, where the choice at stage i is based only on the observation of the edges that have appeared by stage i. We show that these choices can be made so that whp the size of the largest component of the graph formed at stage 0.535n is polylogarithmic in n. This resolves a question of Achlioptas. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 19, 75,85, 2001 [source]

A simple solution to the k -core problem

RANDOM STRUCTURES AND ALGORITHMS, Issue 1-2 2007
Svante Janson
Abstract We study the k -core of a random (multi)graph on n vertices with a given degree sequence. We let n ,,. Then, under some regularity conditions on the degree sequences, we give conditions on the asymptotic shape of the degree sequence that imply that with high probability the k -core is empty and other conditions that imply that with high probability the k -core is non-empty and the sizes of its vertex and edge sets satisfy a law of large numbers; under suitable assumptions these are the only two possibilities. In particular, we recover the result by Pittel, Spencer, and Wormald (J Combinator Theory 67 (1996), 111,151) on the existence and size of a k -core in G(n,p) and G(n,m), see also Molloy (Random Struct Algor 27 (2005), 124,135) and Cooper (Random Struct Algor 25 (2004), 353,375). Our method is based on the properties of empirical distributions of independent random variables and leads to simple proofs. © 2006 Wiley Periodicals, Inc. Random Struct. Alg.,, 2007 [source]