Generalized Petersen graphs are an important class of commonly used interconnection networks and have been studied . The total domination number of generalized Petersen graphs P(m,2) is obtained in this paper.
The skewness of a graph G is the minimum number of edges in G whose removal results in a planar graph. In this paper, we determine the skewness of the generalized Petersen graph P（4k, k） and hence a lower bound for ...The skewness of a graph G is the minimum number of edges in G whose removal results in a planar graph. In this paper, we determine the skewness of the generalized Petersen graph P（4k, k） and hence a lower bound for the crossing number of P（4k, k）. In addition, an upper bound for the crossing number of P（4k, k） is also given.展开更多
A book embedding of a graph G consists of placing the vertices of G on a spine and assigning edges of the graph to pages so that edges in the same page do not cross each other. The page number is a measure of the qual...A book embedding of a graph G consists of placing the vertices of G on a spine and assigning edges of the graph to pages so that edges in the same page do not cross each other. The page number is a measure of the quality of a book embedding which is the minimum number of pages in which the graph G can be embedded. In this paper, the authors discuss the embedding of the generalized Petersen graph and determine that the page number of the generalized Petersen graph is three in some situations, which is best possible.展开更多
Let G be a graph and k be a positive integer. We consider a game with two players Alice and Bob who alternate in coloring the vertices of G with a set of k colors. In every turn, one vertex will be chosen by one playe...Let G be a graph and k be a positive integer. We consider a game with two players Alice and Bob who alternate in coloring the vertices of G with a set of k colors. In every turn, one vertex will be chosen by one player. Alice’s goal is to color all vertices with the k colors, while Bob’s goal is to prevent her. The game chromatic number denoted by?χg(G), is the smallest k such that Alice has a winning strategy with k colors. In this paper, we determine the game chromatic number?χg of circulant graphs?Cn(1,2), , and generalized Petersen graphs GP(n,2), GP(n,3).展开更多
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.展开更多
文摘Generalized Petersen graphs are an important class of commonly used interconnection networks and have been studied . The total domination number of generalized Petersen graphs P(m,2) is obtained in this paper.
文摘The skewness of a graph G is the minimum number of edges in G whose removal results in a planar graph. In this paper, we determine the skewness of the generalized Petersen graph P（4k, k） and hence a lower bound for the crossing number of P（4k, k）. In addition, an upper bound for the crossing number of P（4k, k） is also given.
基金supported by the National Natural Science Foundation of China(Nos.11531010,11401510,11501487)the Key Laboratory Project of Xinjiang(No.2015KL019)the Doctoral Fund of Xinjiang University(No.BS150208)
文摘A book embedding of a graph G consists of placing the vertices of G on a spine and assigning edges of the graph to pages so that edges in the same page do not cross each other. The page number is a measure of the quality of a book embedding which is the minimum number of pages in which the graph G can be embedded. In this paper, the authors discuss the embedding of the generalized Petersen graph and determine that the page number of the generalized Petersen graph is three in some situations, which is best possible.
文摘Let G be a graph and k be a positive integer. We consider a game with two players Alice and Bob who alternate in coloring the vertices of G with a set of k colors. In every turn, one vertex will be chosen by one player. Alice’s goal is to color all vertices with the k colors, while Bob’s goal is to prevent her. The game chromatic number denoted by?χg(G), is the smallest k such that Alice has a winning strategy with k colors. In this paper, we determine the game chromatic number?χg of circulant graphs?Cn(1,2), , and generalized Petersen graphs GP(n,2), GP(n,3).
基金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.
