A dominating induced matching(DIM)of G is an induced matching that dominates every edge of G.In this note,we completely determine the number of DIMs in the generalized Petersen graph P(n,k).We prove that if P(n,k)is a...A dominating induced matching(DIM)of G is an induced matching that dominates every edge of G.In this note,we completely determine the number of DIMs in the generalized Petersen graph P(n,k).We prove that if P(n,k)is a generalized Petersen graph with n=0(mod 5)and k=2,3(mod 5),then E(P(n,k))can be partitioned into five DIMs.Meanwhile,in the left cases k=0,1,4(mod 5),we build some counterexamples to show that there exist some P(n,k)'s which are DIM-free.展开更多
A coloring of G is d-distance if any two vertices at distance at most d from each other get different colors. The minimum number of colors in d-distance colorings of G is its d-distance chromatic number, denoted by χ...A coloring of G is d-distance if any two vertices at distance at most d from each other get different colors. The minimum number of colors in d-distance colorings of G is its d-distance chromatic number, denoted by χd(G). In this paper, we give the exact value of χd(G) (d = 1, 2), for some types of generalized Petersen graphs P(n, k) where k = 1, 2, 3 and arbitrary n.展开更多
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.
Generalized Petersen graphs iare an important class of commonly used in-terconnection networks and have been studied by various researchers. In this paper, weshow that the diameter of generalized Petersen graph P(m, 2...Generalized Petersen graphs iare an important class of commonly used in-terconnection networks and have been studied by various researchers. In this paper, weshow that the diameter of generalized Petersen graph P(m, 2) is O(m/4) and the 3-widediameter of P(m, 2) is O(m/3).展开更多
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.展开更多
A graphG is supereulerian if G has a spanning eulerian subgraph.Boesch et al.[J.Graph Theory,1,79–84（1977）]proposed the problem of characterizing supereulerian graphs.In this paper,we prove that any 3-edge-connecte...A graphG is supereulerian if G has a spanning eulerian subgraph.Boesch et al.[J.Graph Theory,1,79–84（1977）]proposed the problem of characterizing supereulerian graphs.In this paper,we prove that any 3-edge-connected graph with at most 11 edge-cuts of size 3 is supereulerian if and only if it cannot be contractible to the Petersen graph.This extends a former result of Catlin and Lai[J.Combin.Theory,Ser.B,66,123–139（1996）].展开更多
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.展开更多
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.展开更多
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.展开更多
Generalized Petersen graphs are commonly used interconnection networks, and wide diameter is an important parameter to measure fault-tolerance and efficiency of parallel processing computer networks. In this paper, we...Generalized Petersen graphs are commonly used interconnection networks, and wide diameter is an important parameter to measure fault-tolerance and efficiency of parallel processing computer networks. In this paper, we show that the diameter and 3-wide diameter of generalized Petersen graph P（rn, a） are both O（m/2a）, where a ≥ 3.展开更多
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).展开更多
基金Ming Chen was supported by National Key Research and Development Program of China(No.2024YFA1013900)。
文摘A dominating induced matching(DIM)of G is an induced matching that dominates every edge of G.In this note,we completely determine the number of DIMs in the generalized Petersen graph P(n,k).We prove that if P(n,k)is a generalized Petersen graph with n=0(mod 5)and k=2,3(mod 5),then E(P(n,k))can be partitioned into five DIMs.Meanwhile,in the left cases k=0,1,4(mod 5),we build some counterexamples to show that there exist some P(n,k)'s which are DIM-free.
文摘A coloring of G is d-distance if any two vertices at distance at most d from each other get different colors. The minimum number of colors in d-distance colorings of G is its d-distance chromatic number, denoted by χd(G). In this paper, we give the exact value of χd(G) (d = 1, 2), for some types of generalized Petersen graphs P(n, k) where k = 1, 2, 3 and arbitrary n.
文摘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.
基金Supported by NNSF of China(10271114)and(INNSF of China (10301031)
文摘Generalized Petersen graphs iare an important class of commonly used in-terconnection networks and have been studied by various researchers. In this paper, weshow that the diameter of generalized Petersen graph P(m, 2) is O(m/4) and the 3-widediameter of P(m, 2) is O(m/3).
基金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.
基金Supported by National Natural Science Foundation of China(Grant No.11001287)Science Foundation Chongqing Education Committee(Grant Nos.KJ100725 and KJ120731)
文摘A graphG is supereulerian if G has a spanning eulerian subgraph.Boesch et al.[J.Graph Theory,1,79–84（1977）]proposed the problem of characterizing supereulerian graphs.In this paper,we prove that any 3-edge-connected graph with at most 11 edge-cuts of size 3 is supereulerian if and only if it cannot be contractible to the Petersen graph.This extends a former result of Catlin and Lai[J.Combin.Theory,Ser.B,66,123–139（1996）].
文摘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.
文摘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.
文摘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 (Grant No. 60973014)the Excellent Young Teachers Program of Shanghai Municipal Education Conmision (Grant No. B-8101-07-0027)Specialized Research Fund for the Doctoral Program of Higher Education of China (Grant No. 200801411073)
文摘Generalized Petersen graphs are commonly used interconnection networks, and wide diameter is an important parameter to measure fault-tolerance and efficiency of parallel processing computer networks. In this paper, we show that the diameter and 3-wide diameter of generalized Petersen graph P（rn, a） are both O（m/2a）, where a ≥ 3.
文摘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).
