On the Maximum Number of Edges in Topological Graphs with no Four Pairwise Crossing Edges

A topological graph is called k -quasi-planar if it does not contain k pairwise crossing edges. It is conjectured that for every fixed k, the maximum number of edges in a k-quasi-planar graph on n vertices is O(n). We provide an affirmative answer to the case k=4.     

Proper 1-immersions of graphs triangulating the plane

In this paper we study what planar graphs are “rigid” enough such that they can not be drawn on the plane with few (1, 2, or 3) crossings per edge. A graph drawn on the plane is k$k$-immersed in the plane if each edge is crossed by at most k$k$ other edges. By a proper  k$k$-immersion of a graph we mean a k$k$-immersion of the graph in the plane such that there is at least one crossing point. We give a characterization (in terms of forbidden subgraphs) of 4-connected graphs which triangulate the plane and have a proper 1-immersion. We show that every planar graph has a proper 3-immersion.     

Large Families of Cospectral Graphs

Seidel switching is an operation on graphs G satisfyingcertain regularity properties so that the resulting graph Hhas the same spectrum as G. If G issimple then the complement of G and the complementof H are also cospectral. We use a generalizationof Seidel switching to construct exponentially large familiesof cospectral graphs with cospectral complements.     

Large Deviations in Generalized Random Graphs with Node Weights

Generalized random graphs are considered where the presence or absence of an edge depends on the weights of its nodes. Our main interest is to investigate large deviations for the number of edges per node in such a generalized random graph, where the node weights are deterministic under some regularity conditions, as well as chosen i.i.d. from a finite set with positive components. When the node weights are random variables, obstacles arise because the independence among edges no longer exists, our main tools are some results of large deviations for mixtures. After calculating, our results show that the corresponding rate functions for the deterministic case and the random case are very different.     

Topological Subgraphs in Graphs of Large Girth

H of maximum degree , there is an integer g(H) such that every finite graph of minimum degree n and girth at least g(H) contains a subdivision of H. This had been conjectured for in [8]. We prove also that every finite 2n-connected graph of sufficiently large girth is n-linked, and this is best possible for all . Received: February 26, 1997     

Characterization of Product Anti-Magic Graphs of Large Order

A graph G is product anti-magic if one can bijectively label its edges with integers 1, . . . ,e(G) so that no two vertices have the same product of incident labels. This property was introduced by Figueroa-Centeno, Ichishima, and Muntaner-Batle who in particular conjectured that every connected graph with at least 4 vertices is product anti-magic. Here, we completely describe all product anti-magic graphs of sufficiently large order, confirming the above conjecture in this case. Our proof uses probabilistic methods. Reverts to public domain 28 years from publication. Partially supported by the National Science Foundation, Grant DMS-0457512.     

10阶无弓形链环图

证明边数等于10的3‖δ_(v,f)-平图在连通性和顶点最大度条件限制下的三个唯一性结论,进而确定10阶无弓形链环图.     

Biclique-Helly Graphs

A graph is biclique-Helly when its family of (maximal) bicliques is a Helly family. We describe characterizations for biclique-Helly graphs, leading to polynomial time recognition algorithms. In addition, we relate biclique-Helly graphs to the classes of clique-Helly, disk-Helly and neighborhood-Helly graphs.     

Transitive,Locally Finite Median Graphs with Finite Blocks

The subject of this paper are infinite, locally finite, vertex-transitive median graphs. It is shown that the finiteness of the Θ-classes of such graphs does not guarantee finite blocks. Blocks become finite if, in addition, no finite sequence of Θ-contractions produces new cut-vertices. It is proved that there are only finitely many vertex-transitive median graphs of given finite degree with finite blocks. An infinite family of vertex-transitive median graphs with finite intransitive blocks is also constructed and the list of vertex-transitive median graphs of degree four is presented. Sandi Klavžar: Supported by the Ministry of Science of Slovenia under the grant P1-0297. The author is also with the Faculty of Mathematics and Natural Sciences, University of Maribor, Slovenia and the Institute of Mathematics, Physics and Mechanics, Ljubljana.     

Graphs with at most one crossing

The crossing number of a graph $G$ is the least number of crossings over all possible drawings of $G$. We present a structural characterization of graphs with crossing number one.     

零维数等于1的单圈图

The nullity of a graph G is defined to be the multiplicity of the eigenvalue zero in its spectrum. In this paper we characterize the unicyclic graphs with nullity one in aspect of its graphical construction.     

原始图与三次图的可圈度

本文综述关于原始图与三次图的可圈度的近期结果并提出一些未解决的问题。     

Four-Cycled Graphs with Topological Applications

We call a simple graph G a 4-cycled graph if either it has no edges or every edge of it is contained in an induced 4-cycle of G. Our interest on 4-cycled graphs is motivated by the fact that their clique complexes play an important role in the simple-homotopy theory of simplicial complexes. We prove that the minimal simple models within the category of flag simplicial complexes are exactly the clique complexes of some 4-cycled graphs. We further provide structural properties of 4-cycled graphs and describe constructions yielding such graphs. We characterize 4-cycled cographs, and 4-cycled graphs arising from finite chessboards. We introduce a family of inductively constructed graphs, the external extensions, related to an arbitrary graph, and determine the homotopy type of the independence complexes of external extensions of some graphs.     

涉及距离的n-因子临界图

本文证明了如下结论 :设G是 p阶连通图 ,其中 p≡n(mod2 )且n     

Reaction Graphs

Chemical reaction graphs (for a fixed type of rearrangement) are orbital graphs for transitive permutation representations of symmetric groups, so algebraic combinatorics and group theory are effective tools for studying such properties as their connectivity and automorphisms. For example, we construct orbital graphs (and, hence, reaction graphs) from Cayley diagrams by contracting edges, and use graph-embeddings in surfaces to determine the automorphism groups of these graphs. We apply these ideas to the rearrangements of the P ₇ ^3- -ion and of bullvalene, together with some purely mathematical examples of reaction graphs.     

Cycle‐Saturated Graphs with Minimum Number of Edges

A graph G is called H‐saturated if it does not contain any copy of H, but for any edge e in the complement of G, the graph contains some H. The minimum size of an n‐vertex H‐saturated graph is denoted by . We prove holds for all , where is a cycle with length k. A graph G is H‐semisaturated if contains more copies of H than G does for . Let be the minimum size of an n‐vertex H‐semisaturated graph. We have We conjecture that our constructions are optimal for . © 2012 Wiley Periodicals, Inc. J. Graph Theory 73: 203–215, 2013     

Characterizing Flag Graphs and Induced Subgraphs of Cartesian Product Graphs

The vertices of the flag graph Φ(P) of a graded poset P are its maximal chains. Two vertices are adjacent whenever two maximal chains differ in exactly one element. In this paper we characterize induced subgraphs of Cartesian product graphs and flag graphs of graded posets. The latter class of graphs lies between isometric and induced subgraphs of Cartesian products in the embedding structure theory. Both characterization use certain edge-labelings of graphs.     

Infinite Rings with Planar Zero-Divisor Graphs

In this article, we give an extension of the Fundamental Theorem of finite dimensional algebras to the case of ?₂-graded algebras. Essentially, the results are the same as in the classical case, except that the notion of a ?₂-graded division algebra needs to be modified. We classify all finite dimensional ?₂-graded division algebras over ? and ?.     

On crossing numbers of geometric proximity graphs

Let P be a set of n points in the plane. A geometric proximity graph on P is a graph where two points are connected by a straight-line segment if they satisfy some prescribed proximity rule. We consider four classes of higher order proximity graphs, namely, the k-nearest neighbor graph, the k-relative neighborhood graph, the k-Gabriel graph and the k-Delaunay graph. For k=0 (k=1 in the case of the k-nearest neighbor graph) these graphs are plane, but for higher values of k in general they contain crossings. In this paper, we provide lower and upper bounds on their minimum and maximum number of crossings. We give general bounds and we also study particular cases that are especially interesting from the viewpoint of applications. These cases include the 1-Delaunay graph and the k-nearest neighbor graph for small values of k.