Home About us Contact
|
Home About us Contact | ||
|
|
||
Infinite Family (infinite + family)
Selected AbstractsFamilies of pairs of graphs with a large number of common cardsJOURNAL OF GRAPH THEORY, Issue 2 2010Andrew Bowler Abstract The vertex-deleted subgraph G,v, obtained from the graph G by deleting the vertex v and all edges incident to v, is called a card of G. The deck of G is the multiset of its unlabelled vertex-deleted subgraphs. The number of common cards of G and H (or between G and H) is the cardinality of the multiset intersection of the decks of G and H. In this article, we present infinite families of pairs of graphs of order n , 4 that have at least common cards; we conjecture that these, along with a small number of other families constructed from them, are the only pairs of graphs having this many common cards, for sufficiently large n. This leads us to propose a new stronger version of the Reconstruction Conjecture. In addition, we present an infinite family of pairs of graphs with the same degree sequence that have common cards, for appropriate values of n, from which we can construct pairs having slightly fewer common cards for all other values of n,10. We also present infinite families of pairs of forests and pairs of trees with and common cards, respectively. We then present new families that have the maximum number of common cards when one graph is connected and the other disconnected. Finally, we present a family with a large number of common cards, where one graph is a tree and the other unicyclic, and discuss how many cards are required to determine whether a graph is a tree. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 146,163, 2010 [source] Crossing numbers of sequences of graphs II: Planar tilesJOURNAL OF GRAPH THEORY, Issue 4 2003Benny Pinontoan Abstract We describe a method of creating an infinite family of crossing-critical graphs from a single small planar map, the tile, by gluing together many copies of the tile together in a circular fashion. This method yields all known infinite families of k -crossing-critical graphs. Furthermore, the method yields new infinite families, which extend from (4,6) to (3.5,6) the interval of rationals r for which there is, for some k, an infinite sequence of k -crossing-critical graphs all having average degree r. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 332,341, 2003 [source] Minimum linear gossip graphs and maximal linear (,, k)-gossip graphs ,NETWORKS: AN INTERNATIONAL JOURNAL, Issue 3 2001Pierre Fraigniaud Abstract Gossiping is an information dissemination problem in which each node of a communication network has a unique piece of information that must be transmitted to all other nodes using two-way communications between pairs of nodes along the communication links of the network. In this paper, we study gossiping using a linear-cost model of communication which includes a start-up time and a propagation time which is proportional to the amount of information transmitted. A minimum linear gossip graph is a graph (modeling a network), with the minimum possible number of links, in which gossiping can be completed in minimum time under the linear-cost model. For networks with an even number of nodes, we prove that the structure of minimum linear gossip graphs is independent of the relative values of the start-up and unit propagation times. We prove that this is not true when the number of nodes is odd. We present four infinite families of minimum linear gossip graphs. We also present minimum linear gossip graphs for all even numbers of nodes n , 32 except n = 22. A linear (,, k)- gossip graph is a graph with maximum degree , in which gossiping can be completed in k rounds with minimum propagation time. We present three infinite families of maximal linear (,, k)- gossip graphs, that is, linear (,, k)-gossip graphs with a maximum number of nodes. We show that not all minimum broadcast graphs are maximal linear (,, k)-gossip graphs. © 2001 John Wiley & Sons, Inc. [source] Edge-transitive lattice netsACTA CRYSTALLOGRAPHICA SECTION A, Issue 5 2009Olaf Delgado-Friedrichs Lattice nets have one vertex in the topological unit cell. Some two- and three-periodic lattice nets with one kind of edge (edge-transitive) are described. Simple expressions for the topological density of the two-periodic nets are found empirically. Thirteen infinite families of three-periodic cubic lattice nets and hexagonal, trigonal and tetragonal families are identified. [source] Families of pairs of graphs with a large number of common cardsJOURNAL OF GRAPH THEORY, Issue 2 2010Andrew Bowler Abstract The vertex-deleted subgraph G,v, obtained from the graph G by deleting the vertex v and all edges incident to v, is called a card of G. The deck of G is the multiset of its unlabelled vertex-deleted subgraphs. The number of common cards of G and H (or between G and H) is the cardinality of the multiset intersection of the decks of G and H. In this article, we present infinite families of pairs of graphs of order n , 4 that have at least common cards; we conjecture that these, along with a small number of other families constructed from them, are the only pairs of graphs having this many common cards, for sufficiently large n. This leads us to propose a new stronger version of the Reconstruction Conjecture. In addition, we present an infinite family of pairs of graphs with the same degree sequence that have common cards, for appropriate values of n, from which we can construct pairs having slightly fewer common cards for all other values of n,10. We also present infinite families of pairs of forests and pairs of trees with and common cards, respectively. We then present new families that have the maximum number of common cards when one graph is connected and the other disconnected. Finally, we present a family with a large number of common cards, where one graph is a tree and the other unicyclic, and discuss how many cards are required to determine whether a graph is a tree. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 146,163, 2010 [source] Proof of a conjecture on fractional Ramsey numbersJOURNAL OF GRAPH THEORY, Issue 2 2010Jason Brown Abstract Jacobson, Levin, and Scheinerman introduced the fractional Ramsey function rf (a1, a2, ,, ak) as an extension of the classical definition for Ramsey numbers. They determined an exact formula for the fractional Ramsey function for the case k=2. In this article, we answer an open problem by determining an explicit formula for the general case k>2 by constructing an infinite family of circulant graphs for which the independence numbers can be computed explicitly. This construction gives us two further results: a new (infinite) family of star extremal graphs which are a superset of many of the families currently known in the literature, and a broad generalization of known results on the chromatic number of integer distance graphs. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 164,178, 2010 [source] Total domination in 2-connected graphs and in graphs with no induced 6-cyclesJOURNAL OF GRAPH THEORY, Issue 1 2009Michael A. Henning Abstract A set S of vertices in a graph G is a total dominating set of G if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a total dominating set of G is the total domination number ,t(G) of G. It is known [J Graph Theory 35 (2000), 21,45] that if G is a connected graph of order n,>,10 with minimum degree at least 2, then ,t(G),,,4n/7 and the (infinite family of) graphs of large order that achieve equality in this bound are characterized. In this article, we improve this upper bound of 4n/7 for 2-connected graphs, as well as for connected graphs with no induced 6-cycle. We prove that if G is a 2-connected graph of order n,>,18, then ,t(G),,,6n/11. Our proof is an interplay between graph theory and transversals in hypergraphs. We also prove that if G is a connected graph of order n,>,18 with minimum degree at least 2 and no induced 6-cycle, then ,t(G),,,6n/11. Both bounds are shown to be sharp. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 55,79, 2009 [source] Crossing numbers of sequences of graphs II: Planar tilesJOURNAL OF GRAPH THEORY, Issue 4 2003Benny Pinontoan Abstract We describe a method of creating an infinite family of crossing-critical graphs from a single small planar map, the tile, by gluing together many copies of the tile together in a circular fashion. This method yields all known infinite families of k -crossing-critical graphs. Furthermore, the method yields new infinite families, which extend from (4,6) to (3.5,6) the interval of rationals r for which there is, for some k, an infinite sequence of k -crossing-critical graphs all having average degree r. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 332,341, 2003 [source] Nowhere-zero 3-flows in locally connected graphsJOURNAL OF GRAPH THEORY, Issue 3 2003Hong-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] An infinite family of generalized Kalnajs discsMONTHLY NOTICES OF THE ROYAL ASTRONOMICAL SOCIETY, Issue 4 2006Guillermo A. González ABSTRACT An infinite family of axially symmetric thin discs of finite radius is presented. The family of discs is obtained by means of a method developed by Hunter and contains, as its first member, the Kalnajs disc. The surface densities of the discs present a maximum at the centre of the disc and then decrease smoothly to zero at the edge, in such a way that the mass distribution of the higher members of the family is more concentrated at the centre. The first member of the family has a circular velocity proportional to the radius, thus representing a uniformly rotating disc. On the other hand, the circular velocities of the other members of the family increase from a value of zero at the centre of the discs to a maximum and then decrease smoothly to a finite value at the edge of the discs, in such a way that, for the higher members of the family, the maximum value of the circular velocity is attained nearest the centre of the discs. [source] One-bit sigma-delta quantization with exponential accuracyCOMMUNICATIONS ON PURE & APPLIED MATHEMATICS, Issue 11 2003C. Si, nan Güntürk One-bit quantization is a method of representing bandlimited signals by ±1 sequences that are computed from regularly spaced samples of these signals; as the sampling density , , ,, convolving these one-bit sequences with appropriately chosen filters produces increasingly close approximations of the original signals. This method is widely used for analog-to-digital and digital-to-analog conversion, because it is less expensive and simpler to implement than the more familiar critical sampling followed by fine-resolution quantization. However, unlike fine-resolution quantization, the accuracy of one-bit quantization is not well-understood. A natural error lower bound that decreases like 2,, can easily be given using information theoretic arguments. Yet, no one-bit quantization algorithm was known with an error decay estimate even close to exponential decay. In this paper, we construct an infinite family of one-bit sigma-delta quantization schemes that achieves this goal. In particular, using this family, we prove that the error signal for ,-bandlimited signals is at most O(2,.07,). © 2003 Wiley Periodicals, Inc. [source] | ||||||||||