共查询到20条相似文献,搜索用时 15 毫秒
1.
2.
Guoli Ding Bogdan OporowskiRobin Thomas Dirk Vertigan 《Journal of Combinatorial Theory, Series B》2011,101(2):111-121
We prove that, for every positive integer k, there is an integer N such that every 4-connected non-planar graph with at least N vertices has a minor isomorphic to K4,k, the graph obtained from a cycle of length 2k+1 by adding an edge joining every pair of vertices at distance exactly k, or the graph obtained from a cycle of length k by adding two vertices adjacent to each other and to every vertex on the cycle. We also prove a version of this for subdivisions rather than minors, and relax the connectivity to allow 3-cuts with one side planar and of bounded size. We deduce that for every integer k there are only finitely many 3-connected 2-crossing-critical graphs with no subdivision isomorphic to the graph obtained from a cycle of length 2k by joining all pairs of diagonally opposite vertices. 相似文献
3.
We investigate the problem that at least how many edges must a maximal triangle-free graph on n vertices have if the maximal valency is ≤D. Denote this minimum value by F(n, D). For large enough n, we determine the exact value of F(n, D) if D ≥ (n ? 2)/2 and we prove that lim F(n, cn)/n = K(c) exists for all 0 < c with the possible exception of a sequence ck → 0. The determination of K(c) is a finite problem on all intervals [γ, ∞). For D = cn?, 1/2 < ? < 1, we give upper and lower bounds for F(n, D) differing only in a constant factor. (Clearly, D < (n - 1)1/2 is impossible in a maximal triangle-free graph.) 相似文献
4.
Text
We present a construction of expander graphs obtained from Cayley graphs of narrow ray class groups, whose eigenvalue bounds follow from the Generalized Riemann Hypothesis. Our result implies that the Cayley graph of ∗(Z/qZ) with respect to small prime generators is an expander. As another application, we show that the graph of small prime degree isogenies between ordinary elliptic curves achieves nonnegligible eigenvalue separation, and explain the relationship between the expansion properties of these graphs and the security of the elliptic curve discrete logarithm problem.Video
For a video summary of this paper, please visit http://www.youtube.com/watch?v=7jwxmKWWsyM. 相似文献5.
Amru Hussein 《Journal of Evolution Equations》2014,14(2):477-497
For a finite not necessarily compact metric graph, one considers the differential expression ${-\frac{d^2}{d x^2}}$ on each edge. The boundary conditions at the vertices of the graph yielding quasi-m-accretive as well as m-accretive operators are completely characterised. 相似文献
6.
Haruhiko Ogasawara 《Journal of multivariate analysis》2010,101(9):2149-2167
Asymptotic expansions of the distributions of the pivotal statistics involving log-likelihood derivatives under possible model misspecification are derived using the asymptotic cumulants up to the fourth-order and the higher-order asymptotic variance. The pivots dealt with are the studentized ones by the estimated expected information, the negative Hessian matrix, the sum of products of gradient vectors, and the so-called sandwich estimator. It is shown that the first three asymptotic cumulants are the same over the pivots under correct model specification with a general condition of the equalities. An application is given in item response theory, where the observed information is usually used rather than the estimated expected one. 相似文献
7.
8.
The cell rotation graph D(G) on the strongly connected orientations of a 2-edge-connected plane graph G is defined. It is shown that D(G) is a directed forest and every component is an in-tree with one root; if T is a component of D(G), the reversions of all orientations in T induce a component of D(G), denoted by T−, thus (T,T−) is called a pair of in-trees of D(G); G is Eulerian if and only if D(G) has an odd number of components (all Eulerian orientations of G induce the same component of D(G)); the width and height of T are equal to that of T−, respectively. Further it is shown that the pair of directed tree structures on the perfect matchings of a plane elementary bipartite graph G coincide with a pair of in-trees of D(G). Accordingly, such a pair of in-trees on the perfect matchings of any plane bipartite graph have the same width and height. 相似文献
9.
Shiow-Yu Chang 《Proceedings of the American Mathematical Society》2004,132(2):535-541
A new maximal theorem for -majorized correspondences in noncompact spaces is presented and applied to obtain an equilibrium existence theorem for noncompact abstract economies. The corresponding results of Borglin and Keiding (1976), Yannelis and Prabhakar (1983), Ding and Tan (1993), Yuan and Tarafdar (1996), and Ding and Yuan (1998) are generalized by our results.
10.
We obtain lower bounds on the size of a maximum matching in a graph satisfying the condition |N(X)| ≥ s for every independent set X of m vertices, thus generalizing results of Faudree, Gould, Jacobson, and Schelp for the case m = 2. 相似文献
11.
Goh Chee Ying Koh Khee Meng Bruce E. Sagan Vincent R. Vatter 《Journal of Graph Theory》2006,53(4):270-282
We find the maximum number of maximal independent sets in two families of graphs. The first family consists of all graphs with n vertices and at most r cycles. The second family is all graphs of the first family which are connected and satisfy n ≥ 3r. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 270–282, 2006 相似文献
12.
We derive a lower bound on the number of points of a partial linear space of girth 5. As an application, certain strongly regular graphs with=2 are ruled out by observing that the first subconstituents are partial linear spaces. 相似文献
13.
It is proved that, with a possible exception of a finite number of points, the dimension of the eigenspace of a Toeplitz operator with rational matrix symbol, does not exceed the minimum of the dimensions of the eigenspaces corresponding to nearby eigenvalues. This is derived from a more general result concerning eigenspaces of certain Toeplitz operators with matrix symbols, which depend polynomially on a parameter. 相似文献
14.
M. Rašajski Z. Radosavljevi? B. Mihailovi? 《Linear algebra and its applications》2011,435(10):2530-2543
Cacti, or treelike graphs, are graphs whose all cycles are mutually edge-disjoint. Graphs with the property are called reflexive graphs, where λ2 is the second largest eigenvalue of the corresponding (0, 1)-adjacency matrix. The property is a hereditary one, i.e. all induced subgraphs of a reflexive graph are also reflexive. This is why we represent reflexive graphs through the maximal graphs within a given class (such as connected cacti with a fixed number of cycles). In previous work we have determined all maximal reflexive cacti with four cycles whose cycles do not form a bundle and pointed out the role of so-called pouring of Smith graphs in their construction. In this paper, besides pouring, we show several other patterns of the appearance of Smith trees in those constructions. These include splitting of a Smith tree, adding an edge to a Smith tree and then splitting of the resulting graph, identifying two vertices of a Smith tree and then splitting the resulting graph. Our results show that the presence of Smith trees is evident in all such maximal reflexive cacti with four cycles and that in most of them Smith graphs appear in the described way. 相似文献
15.
Let m(G) denote the number of maximal independent sets of vertices in a graph G and let c(n,r) be the maximum value of m(G) over all connected graphs with n vertices and at most r cycles. A theorem of Griggs, Grinstead, and Guichard gives a formula for c(n,r) when r is large relative to n, while a theorem of Goh, Koh, Sagan, and Vatter does the same when r is small relative to n. We complete the determination of c(n,r) for all n and r and characterize the extremal graphs. Problems for maximum independent sets are also completely resolved. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 283–314, 2006 相似文献
16.
17.
A survey of various aspects of the theory and application of degeneracy graphs (DGs for short) is given. The notion and some basic properties of DGs are introduced, cycling of the simplex method is discussed, the neighborhood problem is tackled, and the application of the so-called optimum DGs to particular problems which are connected with optimal degenerate solutions of a linear programming problem is presented. The impact of weakly redundant constraints on various postoptimal analyses under degeneracy is briefly described. 相似文献
18.
19.
Muhammad Akram Saba Siddique Bijan Davvaz 《Journal of Applied Mathematics and Computing》2018,57(1-2):279-302
A neutrosophic set is a generalization of an intuitionistic fuzzy set. Neutrosophic models give more flexibility, precisions and compatibility to the system as compared to intuitionistic fuzzy models. In this research study, we apply the concept of neutrosophic sets to graphs and discuss certain concepts of single-valued neutrosophic graphs. We illustrate the concepts by several examples. We investigate some interesting properties. We describe an application of single-valued neutrosophic graph in decision making process. We also present the procedure of our proposed method as an algorithm. 相似文献
20.
O. V. Borodin 《Journal of Graph Theory》1996,21(2):183-186
If in a plane graph with minimum degree ≥3 no two triangles have an edge in common, then: (1) there are two adjacent vertices with degree sum at most 9, and (2) there is a face of size between 4 and 9 or a 10-face incident with ten 3-vertices. It follows that every planar graph without cycles between 4 and 9 is 3-colorable. © 1996 John Wiley & Sons, Inc. 相似文献