共查询到20条相似文献,搜索用时 31 毫秒
1.
Acta Mathematicae Applicatae Sinica, English Series - A mixed graph $${\tilde G}$$ is obtained by orienting some edges of G, where G is the underlying graph of $${\tilde G}$$ . The positive inertia... 相似文献
2.
We define the notion of a geometric graph in . This is a graph drawn in with its vertices drawn as points and its edges as straight line segments connecting corresponding points. We call two disjoint
edges of G strongly avoiding if there exists an orthogonal projection of to a two dimensional plane H such that the projections of the two edges on H are contained in two different rays, respectively, with a common apex that create a non-acute angle. We show that a geometric
graph on n vertices in with no pair of strongly avoiding edges has at most 2n − 2 edges. As a consequence we get a new proof to Vázsonyi’s conjecture about the maximum number of diameters in a set of
n points in .
This research was supported by THE ISRELI SCIENCE FOUNDATION (grant No.
938/06). 相似文献
3.
Positivity - A distinguished class of polyhedral cones is considered. For a linear operator $$\mathcal {L}$$ preserving a cone in this class, we prove, under some assumption on the number of edges... 相似文献
4.
Derevyanko N. M. Zhukovskii M. E. Rassias M. Skorkin A. Yu. 《Doklady Mathematics》2019,100(2):478-479
Doklady Mathematics - We have proven that the maximum size k of an induced subgraph of the binomial random graph $$G(n,p)$$ with a given number of edges $$e(k)$$ (under certain conditions on this... 相似文献
5.
Paul Jung 《Journal of Theoretical Probability》2005,18(4):949-955
We show that the critical value for the contact process on a vertex-transitive graph
with finitely many edges added and/or removed is the same as the critical value for the contact process on
. This gives a partial answer to a conjecture of Pemantle and Stacey. 相似文献
6.
This work extends the classical F. and M. Riesz theorem to measures that are boundary values of holomorphic functions defined on wedges in
with edges that are in the class C
1,α.This work was supported in part by NSF INT-0203005, CNPq and FAPESP 相似文献
7.
Sergey Bereg 《Graphs and Combinatorics》2009,25(2):139-144
We study characterizations of generic rigid graphs and generic circuits in the plane using only few decompositions into spanning
trees. Generic rigid graphs in the plane can be characterized by spanning tree decompositions [5,6]. A graph G with n vertices and 2n − 3 edges is generic rigid in the plane if and only if doubling any edge results in a graph which is the union of two spanning
trees. This requires 2n − 3 decompositions into spanning trees. We show that n − 2 decompositions suffice: only edges of G − T can be doubled where T is a spanning tree of G.
A recent result on tensegrity frameworks by Recski [7] implies a characterization of generic circuits in the plane. A graph
G with n vertices and 2n − 2 edges is a generic circuit in the plane if and only if replacing any edge of G by any (possibly new) edge results in a graph which is the union of two spanning trees. This requires decompositions into spanning trees. We show that 2n − 2 decompositions suffice. Let be any circular order of edges of G (i.e. ). The graph G is a generic circuit in the plane if and only if is the union of two spanning trees for any . Furthermore, we show that only n decompositions into spanning trees suffice. 相似文献
8.
J. Komlós 《Combinatorica》1985,5(1):57-65
Given a rooted tree with values associated with then vertices and a setA of directed paths (queries), we describe an algorithm which finds the maximum value of every one of the given paths, and which uses only $$5n + n\log \frac{{\left| A \right| + n}}{n}$$ comparisons. This leads to a spanning tree verification algorithm usingO(n+e) comparisons in a graph withn vertices ande edges. No implementation is offered. 相似文献
9.
We consider random walks with small fixed steps inside of edges of a graph
, prescribing a natural rule of probabilities of jumps over a vertex. We show that after an appropriate rescaling such random walks weakly converge to the natural Brownian motion on
constructed in Ref. 1. 相似文献
10.
An edgee in a 3-connected graphG is contractible if the contraction ofe inG results in a 3-connected graph; otherwisee is non-contractible. In this paper, we prove that the number of non-contractible edges in a 3-connected graph of orderp≥5 is at most $$3p - \left[ {\frac{3}{2}(\sqrt {24p + 25} - 5} \right],$$ and show that this upper bound is the best possible for infinitely many values ofp. 相似文献
11.
A. Ramachandra Rao 《Israel Journal of Mathematics》1968,6(3):261-266
It is proved that the maximum number of cut-vertices in a connected graph withn vertices andm edges is $$max\left\{ {q:m \leqq (_2^{n - q} ) + q} \right\}$$ All the extremal graphs are determined and the corresponding problem for cut-edges is also solved. 相似文献
12.
Corinne Feremans Alexander Grigoriev René Sitters 《4OR: A Quarterly Journal of Operations Research》2006,4(4):319-329
This paper is concerned with a special case of the generalized minimum spanning tree problem. The problem is defined on an undirected graph, where the vertex set is partitioned into clusters, and non-negative costs are associated with the edges. The problem is to find a tree of minimum cost containing at least one vertex in each cluster. We consider a geometric case of the problem where the graph is complete, all vertices are situated in the plane, and Euclidean distance defines the edge cost. We prove that the problem is strongly
-hard even in the case of a special structure of the clustering called grid clustering. We construct an exact exponential time dynamic programming algorithm and, based on this dynamic programming algorithm, we develop a polynomial time approximation scheme for the problem with grid clustering. 相似文献
13.
O. V. Sarafanov 《Journal of Mathematical Sciences》2004,120(2):1195-1239
The C
*-algebra
generated by the operators of pseudodifferential boundary value problems on a manifold
with smooth closed disjoint edges and boundary
is studied. The operators act in the space L
2(
)
L
2(
). The goal of this paper is to describe all (up to an equivalence) irreducible representations of the algebra
Bibliography: 12 titles. 相似文献
14.
H. Bielak 《Periodica Mathematica Hungarica》1987,18(1):27-38
In this paper we prove that the cyclomatic number of a graph whose every 2-edgecolouring contains a monochromatic path witht edges is not less than 3t/4 ? 2. This fact leads to a simple non-probabilistic proof of the following theorem of Beck: $$\begin{array}{*{20}c} {lim inf{{\hat r\left( {P_t } \right)} \mathord{\left/ {\vphantom {{\hat r\left( {P_t } \right)} t}} \right. \kern-\nulldelimiterspace} t} \geqslant {9 \mathord{\left/ {\vphantom {9 4}} \right. \kern-\nulldelimiterspace} 4},} & {t \to \infty ,} \\ \end{array}$$ where \(\hat r(P_t )\) is the size Ramsey number of a pathP t ont edges. We also show that the size Ramsey number of a (q + 1)-edge star with a tail of length one equals 4q ? 2, i.e., it is linear on the number of edges of the graph. Finally, we calculate that the upper bound for the size Ramsey number of a (q + 2)-edge star with a tail of length two is not greater than 5q + 3. 相似文献
15.
B. S. Stechkin 《Mathematical Notes》1975,17(3):252-258
We have established that V(Sp, q; G), namely, the collection of all those edges of an arbitrary n-vertex hypergraph G, whose intersections with set Sp, p vertices, has a cardinality q, satisfies certain identity relations; in particular, if v(Sp q; G) = ¦V(Sp, q; G)¦, then $$\upsilon (S_p ,q;G) = \sum\nolimits_{i \geqslant 0} {( - 1)^i } C_{q + i}^q \sum\nolimits_{S_{q + i} \subset S_p } {\upsilon (S_{q + i} ,q + i;} G).$$ As applications we derive two new combinatorial identities. 相似文献
16.
Noga Alon 《Combinatorica》1986,6(3):201-206
An equivalence graph is a vertex disjoint union of complete graphs. For a graphG, let eq(G) be the minimum number of equivalence subgraphs ofG needed to cover all edges ofG. Similarly, let cc(G) be the minimum number of complete subgraphs ofG needed to cover all its edges. LetH be a graph onn vertices with maximal degree ≦d (and minimal degree ≧1), and letG= \(\bar H\) be its complement. We show that $$\log _2 n - \log _2 d \leqq eq(G) \leqq cc(G) \leqq 2e^2 (d + 1)^2 \log _e n.$$ The lower bound is proved by multilinear techniques (exterior algebra), and its assertion for the complement of ann-cycle settles a problem of Frankl. The upper bound is proved by probabilistic arguments, and it generalizes results of de Caen, Gregory and Pullman. 相似文献
17.
Katherine Crowley 《Geometriae Dedicata》2008,133(1):35-50
Understanding the conditions under which a simplicial complex collapses is a central issue in many problems in topology and
combinatorics. Let K be a finite simplicial complex of dimension three or less endowed with the piecewise Euclidean geometry given by declaring
edges to have unit length, and satisfying the property that every 2-simplex is a face of at most two 3-simplices in K. Our main result is that if |K| is nonpositively curved [in the sense of CAT(0)] then K simplicially collapses to a point. The main tool used in the proof is Forman’s discrete Morse theory, a combinatorial analog
of the classical smooth theory developed in the 1920s. A key ingredient in our proof is a combinatorial analog of the fact
that a minimal surface in has nonpositive Gauss curvature.
相似文献
18.
David Conlon 《Combinatorica》2012,32(2):171-186
We show that, for n large, there must exist at least $$\frac{{n^t }} {{C^{(1 + o(1)t^2 } )}}$$ monochromatic K t s in any two-colouring of the edges of K n , where C??2.18 is an explicitly defined constant. The old lower bound, due to Erd?s [2], and based upon the standard bounds for Ramsey??s theorem, is $$\frac{{n^t }} {{4^{(1 + o(1)t^2 } )}}. $$ 相似文献
19.
We study random graphs with an i.i.d. degree sequence of which the tail of the distribution function
is regularly varying with exponent
. In particular, the degrees have infinite mean. Such random graphs can serve as models for complex networks where degree
power laws are observed. The minimal number of edges between two arbitrary nodes, also called the graph distance or the hopcount,
is investigated when the size of the graph tends to infinity. The paper is part of a sequel of three papers. The other two
papers study the case where
, and
, respectively. The main result of this paper is that the graph distance for
converges in distribution to a random variable with probability mass exclusively on the points
and
. We also consider the case where we condition the degrees to be at most
for some
, where
is the size of the graph. For fixed
and
such that
, the hopcount converges to
in probability, while for
, the hopcount converges to the same limit as for the unconditioned degrees. The proofs use extreme value theory.
AMS 2000 Subject Classifications Primary—60G70; Secondary—05C80 相似文献
20.
L. Pyber 《Combinatorica》1986,6(4):393-398
Let cc(G) denote the least number of complete subgraphs necessary to cover the edges of a graphG. Erd?s conjectured that for a graphG onn vertices $$cc(G) + cc(\bar G) \leqq \frac{1}{4}n^2 + 2$$ ifn is sufficiently large. We prove this conjecture. 相似文献