Home  About us  Contact
 

Degree Sequence (degree + sequence)

Distribution by Scientific Domains
Mathematics and Statistics100%

Selected Abstracts

Families of pairs of graphs with a large number of common cards

JOURNAL OF GRAPH THEORY, Issue 2 2010
Andrew 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]

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]

Moments of graphs in monotone families

JOURNAL OF GRAPH THEORY, Issue 1 2006
Zoltán Füredi
Abstract The kth moment of the degree sequence d1,,,d2,,,,dn of a graph G is . We give asymptotically sharp bounds for ,k(G) when G is in a monotone family. We use these results for the case k,=,2 to improve a result of Pach, Spencer, and Tóth [15]. We answer a question of Erd,s [9] by determining the maximum variance of the degree sequence when G is a triangle-free n -vertex graph. © 2005 Wiley Periodicals, Inc. [source]

Cubic graphs without cut-vertices having the same path layer matrix

JOURNAL OF GRAPH THEORY, Issue 3 2001
Andrey A. Dobrynin
Abstract The path layer matrix (or path degree sequence) of a graph G contains quantitative information about all possible paths in G. The entry (i,j) of this matrix is the number of paths in G having initial vertex i and length j. It is known that there are cubic graphs on 62 vertices having the same path layer matrix (A. A. Dobrynin. J Graph Theory 17 (1993) 1,4). A new upper bound of 36 vertices for the least order of such cubic graphs is established. This bound is realized by cubic graphs without cut-vertices. © 2001 John Wiley & Sons, Inc. J Graph Theory 38: 177,182, 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]

The degree sequences and spectra of scale-free random graphs

RANDOM STRUCTURES AND ALGORITHMS, Issue 2 2006
Jonathan Jordan
Abstract We investigate the degree sequences of scale-free random graphs. We obtain a formula for the limiting proportion of vertices with degree d, confirming non-rigorous arguments of Dorogovtsev, Mendes, and Samukhin (Phys Rev Lett 85 (2000), 4633). We also consider a generalization of the model with more randomization, proving similar results. Finally, we use our results on the degree sequence to show that for certain values of parameters localized eigenfunctions of the adjacency matrix can be found. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006 [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]

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]

The degree sequences and spectra of scale-free random graphs

RANDOM STRUCTURES AND ALGORITHMS, Issue 2 2006
Jonathan Jordan
Abstract We investigate the degree sequences of scale-free random graphs. We obtain a formula for the limiting proportion of vertices with degree d, confirming non-rigorous arguments of Dorogovtsev, Mendes, and Samukhin (Phys Rev Lett 85 (2000), 4633). We also consider a generalization of the model with more randomization, proving similar results. Finally, we use our results on the degree sequence to show that for certain values of parameters localized eigenfunctions of the adjacency matrix can be found. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006 [source]