We introduce the triple crossing number, a variation of the crossing number, of a graph, which is the minimal number of crossing points in all drawings of the graph with only triple crossings. It is defined to be zero...We introduce the triple crossing number, a variation of the crossing number, of a graph, which is the minimal number of crossing points in all drawings of the graph with only triple crossings. It is defined to be zero for planar graphs, and to be infinite for non-planar graphs which do not admit a drawing with only triple crossings. In this paper, we determine the triple crossing numbers for all complete multipartite graphs which include all complete graphs.展开更多
In this paper, two recursive inequalities for crossing numbers of graphs are given by using basic counting method. As their applications, the crossing numbers of K1,3,n and K4,n ／ e are determined, respectively.
In this paper, the crossing numbers of the Cartesian products of a specific 5-vertex graph with a star are given, and thus the result fills up the crossing number list of Cartesian products of all 5-vertex graphs with...In this paper, the crossing numbers of the Cartesian products of a specific 5-vertex graph with a star are given, and thus the result fills up the crossing number list of Cartesian products of all 5-vertex graphs with stars （presented by Marian Klesc）. In addition, we also give an up to date description of Cartesian products of 5-vertex graphs with stars, whose crossing numbers are known.展开更多
In this paper, we discuss the crossing numbers of two one-vertex maps on orientable surfaces. By using a reductive method, we give the crossing number of two one-vertex maps with one face on an orientable surface and ...In this paper, we discuss the crossing numbers of two one-vertex maps on orientable surfaces. By using a reductive method, we give the crossing number of two one-vertex maps with one face on an orientable surface and the crossing number of a one-vertex map with one face and a one-vertex map with two faces on an orientable surface. This provides a lower bound for the crossing number of two general maps on an orientable surface.展开更多
It is well known that finding the crossing number of a graph on nonplanar surfaces is very difficult.In this paper we study the crossing number of the circular graph C（10,4） on the projective plane and determine the...It is well known that finding the crossing number of a graph on nonplanar surfaces is very difficult.In this paper we study the crossing number of the circular graph C（10,4） on the projective plane and determine the nonorientable crossing number sequence of C（10,4）.On the basis of the result,we show that the nonorientable crossing number sequence of C（10,4） is not convex.展开更多
The crossing number of cartesian products of paths and cycles with 5-vertex graphs mostly are known, but only few cartesian products of 5-vertex graphs with star K 1,n are known. In this paper, we will extent those re...The crossing number of cartesian products of paths and cycles with 5-vertex graphs mostly are known, but only few cartesian products of 5-vertex graphs with star K 1,n are known. In this paper, we will extent those results, and determine the crossing numbers of cartesian products of two 5-vertex graphs with star K 1,n .展开更多
A graph is 1-planar if it can be drawn on a plane so that each edge is crossed by at most one other edge. A plane graph with near independent crossings （say NIC-planar graph） is a 1-planar graph with the restriction...A graph is 1-planar if it can be drawn on a plane so that each edge is crossed by at most one other edge. A plane graph with near independent crossings （say NIC-planar graph） is a 1-planar graph with the restriction that for any two crossings the four crossed edges are incident with at most one common vertex. The full characterization of NIC-planar complete and complete multipartite graphs is given in this paper.展开更多
The skewness of a graph G,denoted by sk(G),is the minimum number of edges in G whose removal results in a planar graph.It is an important parameter that measures how close a graph is to planarity,and it is complementa...The skewness of a graph G,denoted by sk(G),is the minimum number of edges in G whose removal results in a planar graph.It is an important parameter that measures how close a graph is to planarity,and it is complementary,and computationally equivalent,to the Maximum Planar Subgraph Problem.For any connected graph G on p vertices and q edges with girth g,one can easily verify that sk(G)≥π(G),whereπ(G)=[q−g/g−2(p−2)],and the graph G is said to beπ-skew if equality holds.The concept ofπ-skew was first proposed by G.L.Chia and C.L.Lee.Theπ-skew graphs with girth 3 are precisely the graphs that contain a triangulation as a spanning subgraph.The purpose of this paper is to explore the properties ofπ-skew graphs.Some families ofπ-skew graphs are obtained by applying these properties,including join of two graphs,complete multipartite graphs and Cartesian product of two graphs.We also discuss the threshold for the existence of a spanning triangulation.Among other results some sufficient conditions regarding the regularity and size of a graph,which ensure a spanning triangulation,are given.展开更多
文摘We introduce the triple crossing number, a variation of the crossing number, of a graph, which is the minimal number of crossing points in all drawings of the graph with only triple crossings. It is defined to be zero for planar graphs, and to be infinite for non-planar graphs which do not admit a drawing with only triple crossings. In this paper, we determine the triple crossing numbers for all complete multipartite graphs which include all complete graphs.
基金The authors are indebted to the referees for their suggestions, which improved the presentation and made it more readable. This work was supported by the National Natural Science Foundation of China （Grant Nos. 11301169, 11371133）, Hunan Provincial Natural Science Foundation of China （Nos. 13J J4110, 14JJ3138）, and Hunan Education Department Talented Foundation （No. 16B028）.
文摘In this paper, two recursive inequalities for crossing numbers of graphs are given by using basic counting method. As their applications, the crossing numbers of K1,3,n and K4,n ／ e are determined, respectively.
基金the National Natural Science Foundation of China （No. 10771062） the Fund for New Century Excellent Talents in University （No. NCET-07-0276）.
文摘In this paper, the crossing numbers of the Cartesian products of a specific 5-vertex graph with a star are given, and thus the result fills up the crossing number list of Cartesian products of all 5-vertex graphs with stars （presented by Marian Klesc）. In addition, we also give an up to date description of Cartesian products of 5-vertex graphs with stars, whose crossing numbers are known.
基金Supported by the National Natural Science Foundation of China (Grant No.10671073)Science and Technology Commission of Shanghai Municipality (Grant No.07XD14011)
文摘In this paper, we discuss the crossing numbers of two one-vertex maps on orientable surfaces. By using a reductive method, we give the crossing number of two one-vertex maps with one face on an orientable surface and the crossing number of a one-vertex map with one face and a one-vertex map with two faces on an orientable surface. This provides a lower bound for the crossing number of two general maps on an orientable surface.
基金Supported by the National Natural Science Foundation of China (Grant No.10671073)the Science and Technology Commission of Shanghai Municipality (Grant No.07XD14011)
文摘It is well known that finding the crossing number of a graph on nonplanar surfaces is very difficult.In this paper we study the crossing number of the circular graph C（10,4） on the projective plane and determine the nonorientable crossing number sequence of C（10,4）.On the basis of the result,we show that the nonorientable crossing number sequence of C（10,4） is not convex.
基金Supported by the Scientific Research Fund of Education Department of Hunan Province(08C518)
文摘The crossing number of cartesian products of paths and cycles with 5-vertex graphs mostly are known, but only few cartesian products of 5-vertex graphs with star K 1,n are known. In this paper, we will extent those results, and determine the crossing numbers of cartesian products of two 5-vertex graphs with star K 1,n .
基金Supported by National Natural Science Foundation of China(Grant Nos.11301410,11201440,11101243)the Natural Science Basic Research Plan in Shaanxi Province of China(Grant No.2013JQ1002)+1 种基金the Specialized Research Fund for the Doctoral Program of Higher Education(Grant No.20130203120021)the Fundamental Research Funds for the Central Universities(Grant Nos.K5051370003,K5051370021)
文摘A graph is 1-planar if it can be drawn on a plane so that each edge is crossed by at most one other edge. A plane graph with near independent crossings （say NIC-planar graph） is a 1-planar graph with the restriction that for any two crossings the four crossed edges are incident with at most one common vertex. The full characterization of NIC-planar complete and complete multipartite graphs is given in this paper.
基金Supported by the National Natural Science Foundation of China(Grant No.11301169)Hu’nan Provincial Natural Science Foundation of China(Grant No.2017JJ2055)Scientific Research Fund of Hu’nan Provincial Education Department(Grant No.18A432)。
文摘The skewness of a graph G,denoted by sk(G),is the minimum number of edges in G whose removal results in a planar graph.It is an important parameter that measures how close a graph is to planarity,and it is complementary,and computationally equivalent,to the Maximum Planar Subgraph Problem.For any connected graph G on p vertices and q edges with girth g,one can easily verify that sk(G)≥π(G),whereπ(G)=[q−g/g−2(p−2)],and the graph G is said to beπ-skew if equality holds.The concept ofπ-skew was first proposed by G.L.Chia and C.L.Lee.Theπ-skew graphs with girth 3 are precisely the graphs that contain a triangulation as a spanning subgraph.The purpose of this paper is to explore the properties ofπ-skew graphs.Some families ofπ-skew graphs are obtained by applying these properties,including join of two graphs,complete multipartite graphs and Cartesian product of two graphs.We also discuss the threshold for the existence of a spanning triangulation.Among other results some sufficient conditions regarding the regularity and size of a graph,which ensure a spanning triangulation,are given.
