Large non-planar graphs and an application to crossing-critical graphs

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.     

Maximal triangle-free graphs with restrictions on the degrees

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 c_k → 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.)     

Expander graphs based on GRH with an application to elliptic curve cryptography

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.     

Maximal quasi-accretive Laplacians on finite metric graphs

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.     

Asymptotic expansions for the pivots using log-likelihood derivatives with an application in item response theory

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.     

Cell rotation graphs of strongly connected orientations of plane graphs with an application

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.     

Maximal elements in noncompact spaces with application to equilibria

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.

     

Maximal matchings in graphs with large neighborhoods of independent vertices

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.     

Maximal independent sets in graphs with at most r cycles

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     

A remark on partial linear spaces of girth 5 with an application to strongly regular graphs

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.     

Maximal invariant neutral subspaces and an application to the algebraic Riccati equation

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.     

Maximal reflexive cacti with four cycles: The approach via Smith graphs

Cacti, or treelike graphs, are graphs whose all cycles are mutually edge-disjoint. Graphs with the property are called reflexive graphs, where λ₂ 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.     

Maximal and maximum independent sets in graphs with at most r cycles

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     

1-平面图的结构性质及其在无圈边染色上的应用

一个图称为是1-平面的如果它可以画在一个平面上使得它的每条边最多交叉另外一条边.本文描述了任意1-平面图中小于等于7度点之邻域的局部结构,解决了由Fabrici和Madaras提出的两个关于1-平面图图类中轻图存在性的问题,证明了每个最大度是△的1-平面图G是无圈列表max{2△-2,△+83}-边可选的.     

Degeneracy graphs: theory and application an updated survey

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.     

New concepts in neutrosophic graphs with application

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.     

Structural properties of plane graphs without adjacent triangles and an application to 3-colorings

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.