共查询到20条相似文献,搜索用时 0 毫秒
1.
José Soares 《Discrete and Computational Geometry》1994,11(1):213-233
Given an undirected edge-weighted graphG=(V,E), a subgraphG′=(V,E′) is at-spanner ofG if, for everyu, v∈V, the weighted distance betweenu andv inG′ is at mostt times the weighted distance betweenu andv inG.
We consider the problem of approximating the distances among points of a Euclidean metric space: given a finite setV of points in ℝd, we want to construct a sparset-spanner of the complete weighted graph induced byV. The weight of an edge in these graphs is the Euclidean distance between the endpoints of the edge.
We show by a simple greedy argument that, for anyt>1 and anyV ⊂ ℝd, at-spannerG ofV exists such thatG has degree bounded by a function ofd andt. The analysis of our bounded degree spanners improves over previously known upper bounds on the minimum number of edges of
Euclideant-spanners, even compared with spanners of boundedaverage degree. Our results answer two open problems, one proposed by Vaidya and the other by Keil and Gutwin.
The main result of the paper concerns the case of dimensiond=2. It is fairly easy to see that, for somet (t≥7.6),t-spanners of maximum degree 6 exist for any set of points in the Euclidean plane, but it was not known that degree 5 would
suffice. We prove that for some (fixed)t, t-spanners of degree 5 exist for any set of points in the plane. We do not know if 5 is the best possible upper bound on the
degree.
This research was supported by Conselho Nacional de Desenvolvimento Cientifico e Tecnológico, Proc 203039/87.4 (Brazil). 相似文献
2.
Pavel Chebotarev 《Discrete Applied Mathematics》2012,160(10-11):1484-1500
3.
Let G be a graph of order n. We show that if G is a 2-connected graph and max{d(u), d(v)} + |N(u) U N(v)| ≥ n for each pair of vertices u, v at distance two, then either G is hamiltonian or G ?3Kn/3 U T1 U T2, where n ? O (mod 3), and T1 and T2 are the edge sets of two vertex disjoint triangles containing exactly one vertex from each Kn/3. This result generalizes both Fan's and Lindquester's results as well as several others. 相似文献
4.
5.
William M. Kantor 《Israel Journal of Mathematics》1982,41(4):298-312
Spreads of finite symplectic, orthogonal and unitary vector spaces are used to construct new strongly regular graphs having
the same parameters as the perpendicularity graphs of the underlying vector spaces. Some of the graphs are related to partial
geometries, while others produce interesting symmetric designs. 相似文献
6.
7.
Michaël Rao 《Discrete Mathematics》2008,308(24):6157-6165
Let G be a graph and u be a vertex of G. We consider the following operation: add a new vertex v such that v does not distinguish any two vertices which are not distinguished by u. We call this operation a one-vertex extension. Adding a true twin, a false twin or a pendant vertex are cases of one-vertex extensions. Here we are interested in graph classes defined by a subset of allowed one-vertex extension. Examples are trees, cographs and distance-hereditary graphs. We give a complete classification of theses classes with respect to their clique-width. We also introduce a new graph parameter called the modular-width, and we give a relation with the clique-width. 相似文献
8.
Consider a graph G with two distinguished sets of vertices: the voters and the candidates. A voter v prefers candidate x to candidate y if d(v, x) < d(v, y). This preference relation defines an asymmetric digraph whose vertices are the candidates, in which there is an arc from candidate x to candidate y if and only if more voters prefer x to y than prefer y to x. T. W. Johnson and P. J. Slater (“Realization of Majority Preference Digraphs by Graphically Determined Voting Patterns,” Congressus Numerantium, vol. 67 [1988] 175-186) have shown that each asymmetric digraph of order n can be realized in this way using a graph of order O(n2). We present a new construction reducing the quadratic upper bound to a linear bound. © 1995 John Wiley & Sons, Inc. 相似文献
9.
He-Xi Ye 《Discrete Mathematics》2009,309(4):1001-3257
Let f(t,k) be the maximum diameter of graphs obtained by deleting t edges from a (t+1)-edge-connected graph with diameter k. This paper shows for t≥4, which corrects an improper result in [C. Peyrat, Diameter vulnerability of graphs, Discrete Appl. Math. 9 (3) (1984) 245-250] and also determines f(2,k)=3k−1 and f(3,k)=4k−2 for k≥3. 相似文献
10.
Sascha Bachmann Matthias Reitzner 《Stochastic Processes and their Applications》2018,128(10):3327-3352
Concentration bounds for the probabilities and are proved, where is a median or the expectation of a subgraph count associated with a random geometric graph built over a Poisson process. The lower tail bounds have a Gaussian decay and the upper tail inequalities satisfy an optimality condition. A remarkable feature is that the underlying Poisson process can have a.s. infinitely many points.The estimates for subgraph counts follow from tail inequalities for more general local Poisson U-statistics. These bounds are proved using recent general concentration results for Poisson U-statistics and techniques involving the convex distance for Poisson processes. 相似文献
11.
Zoltán Szigeti 《Combinatorica》1996,16(2):233-241
A. Frank described in [1] an algorithm to determine the minimum number of edges in a graph G whose contraction leaves a factor-critical graph and he asked if there was an algorithm for the weighted version of the problem. We prove that the minimal critical-making edge-sets form the bases of a matroid and hence the matroid greedy algorithm gives rise to the desired algorithm.Partially supported by OTKA F014919, OTKA T17181 and OTKA T17580. 相似文献
12.
Zhao Zhang 《Discrete Mathematics》2006,306(7):705-710
A graph G is said to be hyper-connected if the removal of every minimum cut creates exactly two connected components, one of which is an isolated vertex. In this paper, we first generalize the concept of hyper-connected graphs to that of semi-hyper-connected graphs: a graph G is called semi-hyper-connected if the removal of every minimum cut of G creates exactly two components. Then we characterize semi-hyper-connected edge transitive graphs. 相似文献
13.
Let G be an undirected simple connected graph, and e = uv be an edge of G. Let N
G(e) be the subgraph of G induced by the set of all vertices of G which are not incident to e but are adjacent to u or v. Let N
e be the class of all graphs H such that, for some graph G,N
G
(e) H for every edge e of G. Zelinka [3] studied edge neighborhood graphs and obtained some special graphs in N
e. Balasubramanian and Alsardary [1] obtained some other graphs in N
e. In this paper we given some new graphs in N
e. 相似文献
14.
A graph G is said to be super-connected if any minimum cut of G isolates a vertex. In a previous work due to the second author of this note, super-connected graphs which are both vertex transitive and edge transitive are characterized. In this note, we generalize the characterization to edge transitive graphs which are not necessarily vertex transitive, showing that the only irreducible edge transitive graphs which are not super-connected are the cycles Cn(n?6) and the line graph of the 3-cube, where irreducible means the graph has no vertices with the same neighbor set. Furthermore, we give some sufficient conditions for reducible edge transitive graphs to be super-connected. 相似文献
15.
An induced matching of a graph G is a matching having no two edges joined by an edge. An efficient edge dominating set of G is an induced matching M such that every other edge of G is adjacent to some edge in M. We relate maximum induced matchings and efficient edge dominating sets, showing that efficient edge dominating sets are maximum induced matchings, and that maximum induced matchings on regular graphs with efficient edge dominating sets are efficient edge dominating sets. A necessary condition for the existence of efficient edge dominating sets in terms of spectra of graphs is established. We also prove that, for arbitrary fixed p≥3, deciding on the existence of efficient edge dominating sets on p-regular graphs is NP-complete. 相似文献
16.
17.
Ioan Tomescu 《Discrete Applied Mathematics》2010,158(15):1714-1717
The concept of degree distance of a connected graph G is a variation of the well-known Wiener index, in which the degrees of vertices are also involved. It is defined by D′(G)=∑x∈V(G)d(x)∑y∈V(G)d(x,y), where d(x) and d(x,y) are the degree of x and the distance between x and y, respectively. In this paper it is proved that connected graphs of order n≥4 having the smallest degree distances are K1,n−1,BS(n−3,1) and K1,n−1+e (in this order), where BS(n−3,1) denotes the bistar consisting of vertex disjoint stars K1,n−3 and K1,1 with central vertices joined by an edge. 相似文献
18.
G. Elekes 《Combinatorica》1995,15(2):167-174
Fort fixed,n+t pointsA
1,A
2,...,A
n
andB
1,B
2,...,B
t are constructed in the plane withO(n) distinct distancesd(A
i
B
j
) As a by-product we show that the graph of thek largest distances can contain a complete subgraphK
t, n
withn=(k
2), which settles a problem of Erds, Lovász and Vesztergombi.Research partially supported by the Hungarian National Science Fund (OTKA) # 2117. 相似文献
19.
20.