Domains of Holomorphy with Edges and Lower Dimensional Boundary Singularities

It is shown that a domain in C ^N with piecewise smooth boundary (and also of some more general shape) is a domain of holomorphy, provided the Levi form at every regular point is positively semidefinite and the tangent cone is convex at every point outside a boundary subset of zero Hausdorff (2N-2)-dimensional measure.     

Geometric Graphs with Few Disjoint Edges

A geometric graph is a graph drawn in the plane so that the vertices are represented by points in general position, the edges are represented by straight line segments connecting the corresponding points. Improving a result of Pach and T?rőcsik, we show that a geometric graph on n vertices with no k+1 pairwise disjoint edges has at most k ³ (n+1) edges. On the other hand, we construct geometric graphs with n vertices and approximately (3/2)(k-1)n edges, containing no k+1 pairwise disjoint edges. We also improve both the lower and upper bounds of Goddard, Katchalski, and Kleitman on the maximum number of edges in a geometric graph with no four pairwise disjoint edges. Received May 7, 1998, and in revised form March 24, 1999.     

Bipartite Intrinsically Knotted Graphs with 22 Edges

A graph is intrinsically knotted if every embedding contains a nontrivially knotted cycle. It is known that intrinsically knotted graphs have at least 21 edges and that the KS graphs, K₇ and the 13 graphs obtained from K₇ by moves, are the only minor minimal intrinsically knotted graphs with 21 edges [1, 9, 11, 12]. This set includes exactly one bipartite graph, the Heawood graph. In this article we classify the intrinsically knotted bipartite graphs with at most 22 edges. Previously known examples of intrinsically knotted graphs of size 22 were those with KS graph minor and the 168 graphs in the K_{3, 3, 1, 1} and families. Among these, the only bipartite example with no Heawood subgraph is Cousin 110 of the family. We show that, in fact, this is a complete listing. That is, there are exactly two graphs of size at most 22 that are minor minimal bipartite intrinsically knotted: the Heawood graph and Cousin 110.     

Geometric Graphs with No Three Disjoint Edges

A geometric graph is a graph drawn in the plane so that the vertices are represented by points in general position and edges are represented by straight line segments. We show that a geometric graph on n vertices with no three pairwise disjoint edges has at most 2.5n edges. This result is tight up to an additive constant.     

加边与删边运算下图的亏格分布

设(G,u,v)是以u和u为根的双根连通图,用边e连接点u和v,所得之图记为G+E.Gross对根u和v的度均为2的情形,给出了G+e的亏格分布与(G,u,v)的部分亏格分布之间的一个关系.本文推广到有一个根的度可以任意大的情形,并由(G,u,v)的部分亏格分布导出了G+e的亏格分布.     

The Least Eigenvalue of Graphs with Cut Edges

In this paper we characterize the unique graph whose least eigenvalue attains the minimum among all connected graphs of fixed order and given number of cut edges.     

The Maximum Number of Edges in Geometric Graphs with Pairwise Virtually Avoiding Edges

Let G be a geometric graph on n vertices that are not necessarily in general position. Assume that no line passing through one edge of G meets the relative interior of another edge. We show that in this case the number of edges in G is at most 2n?3.     

On Graphs Without Multicliqual Edges

An edge which belongs to more than one clique of a given graph is called a multicliqual edge. We find a necessary and sufficient condition for a graph H to be the clique graph of some graph G without multicliqual edges. We also give a characterization of graphs without multicliqual edges that have a unique critical generator. Finally, it is shown that there are infinitely many self-clique graphs having more than one critical generator.     

Disjoint Edges in Complete Topological Graphs

It is shown that every complete $n$ -vertex simple topological graph has at $\varOmega (n^{1/3})$ pairwise disjoint edges, and these edges can be found in polynomial time. This proves a conjecture of Pach and Tóth, which appears as Problem 5 from Chapter 9.5 in Research Problems in Discrete Geometry by Brass, Moser, and Pach.     

Contractible Edges in 7-Connected Graphs

An edge of a k-connected graph is said to be a k-contractible edge, if its contraction yields again a k-connected graph. A noncomplete k-connected graph possessing no k-contractible edges is called contraction critical k-connected. Recently, Kriesell proved that every contraction critical 7-connected graph has two distinct vertices of degree 7. And he guessed that there are two vertices of degree 7 at distance one or two. In this paper, we give a proof to his conjecture. The work partially supported by NNSF of China(Grant number: 10171022)     

恰有k条非基本边的极小3连通图

设G是简单3连通图．G\e(删除边e)和G/e(收缩边e)都不是简单3连通图,则e称为G的基本边．对于3连通图中的非基本边．Tutte证明了：唯一没有非基本边的简单3连通图是轮．Oxley和Wu确定了至多有3条非基本边的所有极小3连通图以及恰有4条非基本的极小3连通图．Reid与Wu确定了至多有5条非基本边的极小3连通图．在本文中,我们在极小3连通图中定义了三种运算,然后通过轮利用这些运算的逆运算给出恰有k(k■2)条非基本边的极小3连通图的一种构造方法．     

The 3-Connected Graphs with Exactly k Non-Essential Edges

Let G be a simple 3-connected graph. An edge e of G is essential if neither the deletion G\ e nor the contraction G/e is both simple and 3-connected. In this study, we show that all 3-connected graphs with k(k ≥ 2) non-essential edges can be obtained from a wheel by three kinds of operations which defined in the paper.     

6连通图中的可收缩边

Kriesell(2001年)猜想：如果κ连通图中任意两个相邻顶点的度的和至少是2[5κ/4]-1则图中有κ-可收缩边．本文证明每一个收缩临界6连通图中有两个相邻的度为6的顶点，由此推出该猜想对κ=6成立。     

On Geometric Graphs with No k Pairwise Parallel Edges

A geometric graph is a graph G=(V,E) drawn in the plane so that the vertex set V consists of points in general position and the edge set E consists of straight-line segments between points of V . Two edges of a geometric graph are said to be parallel if they are opposite sides of a convex quadrilateral. In this paper we show that, for any fixed k ≥ 3 , any geometric graph on n vertices with no k pairwise parallel edges contains at most O(n) edges, and any geometric graph on n vertices with no k pairwise crossing edges contains at most O(n log n) edges. We also prove a conjecture by Kupitz that any geometric graph on n vertices with no pair of parallel edges contains at most 2n-2 edges. <lsiheader> <onlinepub>26 June, 1998 <editor>Editors-in-Chief: &lsilt;a href=../edboard.html#chiefs&lsigt;Jacob E. Goodman, Richard Pollack&lsilt;/a&lsigt; <pdfname>19n3p461.pdf <pdfexist>yes <htmlexist>no <htmlfexist>no <texexist>yes <sectionname> </lsiheader> Received January 27, 1997, and in revised form March 4, 1997, and June 16, 1997.     

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.     

Contractible Edges in k-Connected Graphs with Some Forbidden Subgraphs

In 2001, Kawarabayashi proved that for any odd integer k ≥ 3, if a k-connected graph G is \({K^{-}_{4}}\) -free, then G has a k-contractible edge. He pointed out, by a counterexample, that this result does not hold when k is even. In this paper, we have proved the following two results on the subject: (1) For any even integer k ≥ 4, if a k-connected graph G is \({K_{4}^{-}}\) -free and d _G (x) + d _G (y) ≥ 2k + 1 hold for every two adjacent vertices x and y of V(G), then G has a k-contractible edge. (2) Let t ≥ 3, k ≥ 2t – 1 be integers. If a k-connected graph G is \({(K_{1}+(K_{2} \cup K_{1, t}))}\) -free and d _G (x) + d _G (y) ≥ 2k + 1 hold for every two adjacent vertices x and y of V(G), then G has a k-contractible edge.     

The 3-Connected Graphs with Exactly Three Non-Essential Edges

An edge e of a simple 3-connected graph G is essential if neither the deletion G\e nor the contraction G/e is both simple and 3-connected. Tuttes Wheels Theorem proves that the only simple 3-connected graphs with no non-essential edges are the wheels. In earlier work, as a corollary of a matroid result, the authors determined all simple3-connected graphs with at most two non-essential edges. This paper specifies all such graphs with exactly three non-essential edges. As a consequence, with the exception of the members of 10 classes of graphs, all 3-connected graphs have at least four non-essential edges.Acknowledgments The first author was partially supported by grants from the National Security Agency. The second author was partially supported by the Office of Naval Research under Grant No. N00014-01-1-0917.1991 Mathematics Subject Classification: 05C40Final version received: October 30, 2003     

On the Extremal Zagreb Indices of Graphs with Cut Edges

For a (molecular) graph, the first Zagreb index M ₁ is equal to the sum of squares of the vertex degrees, and the second Zagreb index M ₂ is equal to the sum of products of degrees of pairs of adjacent vertices. In this paper, we show that all connected graphs with n vertices and k cut edges, the maximum (resp. minimum) M ₁- and M ₂-value are obtained, respectively, and uniquely, at K _n ^k (resp. P _n ^k ), where K _n ^k is a graph obtained by joining k independent vertices to one vertex of K _n?k and P _n ^k is a graph obtained by connecting a pendent path P _k+1 to one vertex of C _n?k.     

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     

Erratum to: On the Extremal Zagreb Indices of Graphs with Cut Edges

For a (molecular) graph, the first Zagreb index M ₁ is equal to the sum of squares of the vertex degrees, and the second Zagreb index M ₂ is equal to the sum of products of degrees of pairs of adjacent vertices. In this paper, we show that all connected graphs with n vertices and k cut edges, the maximum (resp. minimum) M ₁- and M ₂-value are obtained, respectively, and uniquely, at K _n ^k (resp. P _n ^k ), where K _n ^k is a graph obtained by joining k independent vertices to one vertex of K _n−k and P _n ^k is a graph obtained by connecting a pendent path P _k+1 to one vertex of C _n−k .