The exact domination number of the generalized Petersen graphs

Let G=(V,E) be a graph. A subset S⊆V is a dominating set of G, if every vertex u∈V−S is dominated by some vertex v∈S. The domination number, denoted by γ(G), is the minimum cardinality of a dominating set. For the generalized Petersen graph G(n), Behzad et al. [A. Behzad, M. Behzad, C.E. Praeger, On the domination number of the generalized Petersen graphs, Discrete Mathematics 308 (2008) 603-610] proved that and conjectured that the upper bound is the exact domination number. In this paper we prove this conjecture.     

On the Hamilton connectivity of generalized Petersen graphs

We investigate the Hamilton connectivity and Hamilton laceability of generalized Petersen graphs whose internal edges have jump 1, 2 or 3.     

Skewness of generalized Petersen graphs and related graphs

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.     

Embedding of circulant graphs and generalized Petersen graphs on projective plane

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.     

All double generalized Petersen graphs are Hamiltonian

The double generalized Petersen graph $DP(n,t)$, $n\ge 3$ and $t\in {\mathbb{Z}}_n?\left\{0\right\}$, $2\le 2t<n$, has vertex-set $\{x_i,y_i,u_i,v_i\mid i\in {\mathbb{Z}}_n\}$, edge-set $\{\{x_i,x_{i+1}\},\{y_i,y_{i+1}\},\{u_i,v_{i+t}\},\{v_i,u_{i+t}\},\{x_i,u_i\},\{y_i,v_i\}\mid i\in {\mathbb{Z}}_n\}$. These graphs were first defined by Zhou and Feng as examples of vertex-transitive non-Cayley graphs. Then, Kutnar and Petecki considered the structural properties, Hamiltonicity properties, vertex-coloring and edge-coloring of $DP(n,t)$, and conjectured that all $DP(n,t)$ are Hamiltonian. In this paper, we prove this conjecture.     

On the domination number of the generalized Petersen graphs

Graph domination numbers and algorithms for finding them have been investigated for numerous classes of graphs, usually for graphs that have some kind of tree-like structure. By contrast, we study an infinite family of regular graphs, the generalized Petersen graphs G(n). We give two procedures that between them produce both upper and lower bounds for the (ordinary) domination number of G(n), and we conjecture that our upper bound ⌈3n/5⌉ is the exact domination number. To our knowledge this is one of the first classes of regular graphs for which such a procedure has been used to estimate the domination number.     

The isomorphism classes of the generalized Petersen graphs

In earlier work involving cycles in Generalized Petersen Graphs, we noticed some unexpected instances of P(m,k)≅P(m,l). In this article, all such instances are characterized. A formula is presented for the number of isomorphism classes of P(m,k).     

The Crossing Number of C(mk;{1, k})

Calculating the crossing number of a given graph is, in general, an elusive problem. Garey and Johnson have proved that the problem of determining the crossing number of an arbitrary graph is NP-complete. The crossing number of a network(graph) is closely related to the minimum layout area required for the implementation of a VLSI circuit for that network. With this important application in mind, it makes most sense to analyze the the crossing number of graphs with good interconnection properties, such as the circulant graphs. In this paper we study the crossing number of the circulant graph C(mk;{1,k}) for m3, k3, give an upper bound of cr(C(mk;{1,k})), and prove that cr(C(3k;{1,k}))=k.Research supported by Chinese Natural Science Foundation     

Embedding Generalized Petersen Graph in Books

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.     

On crossing numbers of geometric proximity graphs

Let P be a set of n points in the plane. A geometric proximity graph on P is a graph where two points are connected by a straight-line segment if they satisfy some prescribed proximity rule. We consider four classes of higher order proximity graphs, namely, the k-nearest neighbor graph, the k-relative neighborhood graph, the k-Gabriel graph and the k-Delaunay graph. For k=0 (k=1 in the case of the k-nearest neighbor graph) these graphs are plane, but for higher values of k in general they contain crossings. In this paper, we provide lower and upper bounds on their minimum and maximum number of crossings. We give general bounds and we also study particular cases that are especially interesting from the viewpoint of applications. These cases include the 1-Delaunay graph and the k-nearest neighbor graph for small values of k.     

Domination in generalized Petersen graphs

Generalized Petersen graphs are certain graphs consisting of one quadratic factor. For these graphs some numerical invariants concerning the domination are studied, namely the domatic number , the total domatic number and the -ply domatic number for and . Some exact values and some inequalities are stated.     

On k-planar crossing numbers

The k-planar crossing number of a graph is the minimum number of crossings of its edges over all possible drawings of the graph in k planes. We propose algorithms and methods for k-planar drawings of general graphs together with lower bound techniques. We give exact results for the k-planar crossing number of K_2k+1,q, for k?2. We prove tight bounds for complete graphs. We also study the rectilinear k-planar crossing number.     

The bondage numbers of graphs with small crossing numbers

The bondage number b(G) of a nonempty graph G is the cardinality of a smallest edge set whose removal from G results in a graph with domination number greater than the domination number γ(G) of G. Kang and Yuan proved b(G)?8 for every connected planar graph G. Fischermann, Rautenbach and Volkmann obtained some further results for connected planar graphs. In this paper, we generalize their results to connected graphs with small crossing numbers.     

广义Petersen图的弱点传递性

图X称为弱点传递图如果X的自同态幺半群EndX在顶点集V(X)上的作用是传递的 .本文给出了广义Petersen图是二分图的充要条件 ,刻划了奇围长小于 9的广义Petersen图的弱点传递性 ,作为推论给出了所有h ≤ 1 5的弱点传递的广义Pe tersen图P(h ,t) .     

两类广义Petersen 图的Euler亏格

广义 Petersen 图 P(n, m) 是这样的一个图:它的顶点集是{u_i, v_i | i=0,1, ^… , n-1}, 边集是 {u_iu_i+1, v_iv_i+m, u_iv_i | i=0,1, ^…, n-1}, 这里 m, n 是正整数、加法是在模n 下且 m<|n/2| . 这篇文章证明了P(2m+1, m)(m≥ 2) 的 Euler 亏格是1, 并且 P(2m+2, m)(m≥ 5) 的 Euler 亏格是2.