In this paper, we consider the family of generalized Petersen graphs P（n,4）. We prove that the metric dimension of P（n, 4） is 3 when n = 0 （mod 4）, and is 4 when n = 4k ＋ 3 （k is even）.For n = 1,2 （mod 4） a...In this paper, we consider the family of generalized Petersen graphs P（n,4）. We prove that the metric dimension of P（n, 4） is 3 when n = 0 （mod 4）, and is 4 when n = 4k ＋ 3 （k is even）.For n = 1,2 （mod 4） and n = 4k ＋ 3 （k is odd）, we prove that the metric dimension of P（n,4） is bounded above by 4. This shows that each graph of the family of generalized Petersen graphs P（n, 4） has constant metric dimension.展开更多
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.展开更多
Both the circulant graph and the generalized Petersen graph are important types of graphs in graph theory. In this paper, the structures of embeddings of circulant graph C（2n ＋ 1; {1, n}） on the projective plane ar...Both the circulant graph and the generalized Petersen graph are important types of graphs in graph theory. In this paper, the structures of embeddings of circulant graph C（2n ＋ 1; {1, n}） on the projective plane are described, the number of embeddings of C（2n ＋ 1; {1, n}） on the projective plane follows, then the number of embeddings of the generalized Petersen graph P（2n ＋ 1, n） on the projective plane is deduced from that of C（2n ＋ 1; {1, n}）, because C（2n ＋ 1; {1, n}） is a minor of P（2n ＋ 1, n）, their structures of embeddings have relations. In the same way, the number of embeddings of the generalized Petersen graph P（2n, 2） on the projective plane is also obtained.展开更多
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.展开更多
The generalized Petersen graphs p(n,k) n≥3, 1≤k<n/2, consist of an outer n-cycle x0x1 x2'''xn--1 , a set of n spokes x,yi (O≤i≤n--1), and n inner edges yiyi+k with indices taken modulo n.This paper ...The generalized Petersen graphs p(n,k) n≥3, 1≤k<n/2, consist of an outer n-cycle x0x1 x2'''xn--1 , a set of n spokes x,yi (O≤i≤n--1), and n inner edges yiyi+k with indices taken modulo n.This paper deals with (a,b)-consecutive labelings of generalized Petersen graph p(n,k).展开更多
文摘In this paper, we consider the family of generalized Petersen graphs P（n,4）. We prove that the metric dimension of P（n, 4） is 3 when n = 0 （mod 4）, and is 4 when n = 4k ＋ 3 （k is even）.For n = 1,2 （mod 4） and n = 4k ＋ 3 （k is odd）, we prove that the metric dimension of P（n,4） is bounded above by 4. This shows that each graph of the family of generalized Petersen graphs P（n, 4） has constant metric dimension.
文摘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.
文摘Both the circulant graph and the generalized Petersen graph are important types of graphs in graph theory. In this paper, the structures of embeddings of circulant graph C（2n ＋ 1; {1, n}） on the projective plane are described, the number of embeddings of C（2n ＋ 1; {1, n}） on the projective plane follows, then the number of embeddings of the generalized Petersen graph P（2n ＋ 1, n） on the projective plane is deduced from that of C（2n ＋ 1; {1, n}）, because C（2n ＋ 1; {1, n}） is a minor of P（2n ＋ 1, n）, their structures of embeddings have relations. In the same way, the number of embeddings of the generalized Petersen graph P（2n, 2） on the projective plane is also obtained.
基金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.
文摘The generalized Petersen graphs p(n,k) n≥3, 1≤k<n/2, consist of an outer n-cycle x0x1 x2'''xn--1 , a set of n spokes x,yi (O≤i≤n--1), and n inner edges yiyi+k with indices taken modulo n.This paper deals with (a,b)-consecutive labelings of generalized Petersen graph p(n,k).
