共查询到20条相似文献,搜索用时 15 毫秒
1.
Jonathan Jordan 《Random Structures and Algorithms》2006,29(2):226-242
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 ( 14 ). 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 相似文献
2.
A better than quadratic estimate is given for the volume of the convex hull of points on Hadamard manifolds with pinched curvature. It was known previously that the volume is bounded by some polynomial in . The estimate comes from the study of the convex hull of finitely many convex sets on Hadamard manifolds.
3.
Let Dn(r) denote the convex hull of degree sequences of simple r-uniform hypergraphs on the vertex set {1,2,…,n}. The polytope Dn(2) is a well-studied object. Its extreme points are the threshold sequences (i.e., degree sequences of threshold graphs) and its facets are given by the Erdös–Gallai inequalities. In this paper we study the polytopes Dn(r) and obtain some partial information. Our approach also yields new, simple proofs of some basic results on Dn(2). Our main results concern the extreme points and facets of Dn(r). We characterize adjacency of extreme points of Dn(r) and, in the case r=2, determine the distance between two given vertices in the graph of Dn(2). We give a characterization of when a linear inequality determines a facet of Dn(r) and use it to bound the sizes of the coefficients appearing in the facet defining inequalities; give a new short proof for the facets of Dn(2); find an explicit family of Erdös–Gallai type facets of Dn(r); and describe a simple lifting procedure that produces a facet of Dn+1(r) from one of Dn(r). 相似文献
4.
Given a bipartite graph with bipartition each spanning tree in has a degree sequence on and one on . Löhne and Rudloff showed that the number of possible degree sequences on equals the number of possible degree sequences on . Their proof uses a non-trivial characterization of degree sequences by -draconian sequences based on polyhedral results of Postnikov. In this paper, we give a purely graph-theoretic proof of their result. 相似文献
5.
Let G be a finite and simple graph with vertex set V(G), and let f:V(G)→{−1,1} be a two-valued function. If ∑x∈N[v]f(x)≥1 for each v∈V(G), where N[v] is the closed neighborhood of v, then f is a signed dominating function on G. A set {f1,f2,…,fd} of signed dominating functions on G with the property that for each x∈V(G), is called a signed dominating family (of functions) on G. The maximum number of functions in a signed dominating family on G is the signed domatic number on G. In this paper, we investigate the signed domatic number of some circulant graphs and of the torus Cp×Cq. 相似文献
6.
A signed graph has a plus or minus sign on each edge. A simple cycle is positive or negative depending on whether it contains an even or odd number of negative edges, respectively. We consider embeddings of a signed graph in the projective plane for which a simple cycle is essential if and only if it is negative. We characterize those signed graphs that have such a projective-planar embedding. Our characterization is in terms of a related signed graph formed by considering the theta subgraphs in the given graph. 相似文献
7.
We view an undirected graph as a symmetric digraph, where each edge is replaced by two opposite arcs and . Assume is an inverse closed subset of permutations of positive integers. We say is --colourable if for any mapping with , there is a mapping such that for each arc . The concept of --colourable is a common generalization of several other colouring concepts. This paper is focused on finding the sets such that every triangle-free planar graph is -3-colourable. Such a set is called TFP-good. Grötzsch’s theorem is equivalent to say that is TFP-good. We prove that for any inverse closed subset of which is not isomorphic to , is TFP-good if and only if either or there exists such that for each , . It remains an open question to determine whether or not is TFP-good. 相似文献
8.
Changping Wang 《Discrete Applied Mathematics》2007,155(11):1497-1505
Let G be a graph with vertex set V(G) and edge set E(G). A function f:E(G)→{-1,1} is said to be a signed star dominating function of G if for every v∈V(G), where EG(v)={uv∈E(G)|u∈V(G)}. The minimum of the values of , taken over all signed star dominating functions f on G, is called the signed star domination number of G and is denoted by γSS(G). In this paper, a sharp upper bound of γSS(G×H) is presented. 相似文献
9.
We consider the set of all graphs on n labeled vertices with prescribed degrees D = (d1,…,dn). For a wide class of tame degree sequences D we obtain a computationally efficient asymptotic formula approximating the number of graphs within a relative error which approaches 0 as n grows. As a corollary, we prove that the structure of a random graph with a given tame degree sequence D is well described by a certain maximum entropy matrix computed from D. We also establish an asymptotic formula for the number of bipartite graphs with prescribed degrees of vertices, or, equivalently, for the number of 0‐1 matrices with prescribed row and column sums. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013 相似文献
10.
11.
12.
The network loading problem (NLP) is a specialized capacitated network design problem in which prescribed point-to-point demand between various pairs of nodes of a network must be met by installing (loading) a capacitated facility. We can load any number of units of the facility on each of the arcs at a specified arc dependent cost. The problem is to determine the number of facilities to be loaded on the arcs that will satisfy the given demand at minimum cost.This paper studies two core subproblems of the NLP. The first problem, motivated by a Lagrangian relaxation approach for solving the problem, considers a multiple commodity, single arc capacitated network design problem. The second problem is a three node network; this specialized network arises in larger networks if we aggregate nodes. In both cases, we develop families of facets and completely characterize the convex hull of feasible solutions to the integer programming formulation of the problems. These results in turn strengthen the formulation of the NLP.Research of this author was supported in part by a Faculty Grant from the Katz Graduate School of Business, University of Pittsburgh. 相似文献
13.
The two-dimensional convex hull algorithms of Graham, Jarvis, Eddy, and Akl and Toussaint are tested on four different planar point distributions. Some modifications are discussed for both the Graham and Jarvis algorithms. Timings taken of FORTRAN implementations indicate that the Eddy and Akl-Toussaint algorithms are superior on uniform distributions of points in the plane. The Graham algorithm outperforms the others on those distributions where most of the points are on or near the boundary of the hull. 相似文献
14.
Let fd (G) denote the minimum number of edges that have to be added to a graph G to transform it into a graph of diameter at most d. We prove that for any graph G with maximum degree D and n > n0 (D) vertices, f2(G) = n − D − 1 and f3(G) ≥ n − O(D3). For d ≥ 4, fd (G) depends strongly on the actual structure of G, not only on the maximum degree of G. We prove that the maximum of fd (G) over all connected graphs on n vertices is n/⌊d/2 ⌋ − O(1). As a byproduct, we show that for the n‐cycle Cn, fd (Cn) = n/(2⌊d/2 ⌋ − 1) − O(1) for every d and n, improving earlier estimates of Chung and Garey in certain ranges. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 161–172, 2000 相似文献
15.
Amitabha Tripathi 《Discrete Applied Mathematics》2008,156(18):3513-3517
A finite sequence of nonnegative integers is called graphic if the terms in the sequence can be realized as the degrees of vertices of a finite simple graph. We present two new characterizations of graphic sequences. The first of these is similar to a result of Havel-Hakimi, and the second equivalent to a result of Erd?s & Gallai, thus providing a short proof of the latter result. We also show how some known results concerning degree sets and degree sequences follow from our results. 相似文献
16.
17.
Amitabha Tripathi 《Discrete Applied Mathematics》2007,155(5):670-671
For a finite simple graph G, we denote the set of degrees of its vertices, known as its degree set, by D(G). Kapoor, Polimeni and Wall [Degree sets for graphs, Fund. Math. 95 (1977) 189-194] have determined the least number of vertices among graphs with a given degree set. We give a very short proof of this result. 相似文献
18.
Ignacio Cascos 《Computational Statistics》2007,22(4):557-569
Given a data set in the multivariate Euclidean space, we study regions of central points built by averaging all their subsets
with a fixed number of elements. The averaging of these sets is performed by appropriately scaling the Minkowski or elementwise
summation of their convex hulls. The volume of such central regions is proposed as a multivariate scatter estimate and a circular
sequence algorithm to compute the central regions of a bivariate data set is described.
Extended version of the conference paper Cascos (2006) presented at the 17th Conference of the European Regional Section of
the International Association for Statistical Computing (COMPSTAT 2006, Rome, Italy, August 28–September 1, 2006).
Supported by the Spanish Ministry of Education and Science under grant MTM2005-02254. 相似文献
19.
A subset A of a Banach space is called Banach–Saks when every sequence in A has a Cesàro convergent subsequence. Our interest here focuses on the following problem: is the convex hull of a Banach–Saks set again Banach–Saks? By means of a combinatorial argument, we show that in general the answer is negative. However, sufficient conditions are given in order to obtain a positive result. 相似文献
20.
Enkelejd Hashorva 《Discrete Applied Mathematics》2011,159(4):201-211
In this paper we consider the convex hull of a spherically symmetric sample in Rd. Our main contributions are some new asymptotic results for the expectation of the number of vertices, number of facets, area and the volume of the convex hull assuming that the marginal distributions are in the Gumbel max-domain of attraction. Further, we briefly discuss two other models assuming that the marginal distributions are regularly varying or O-regularly varying. 相似文献