In this paper we prove that the generalized permutation graph G（n, k） is upper embeddable if it has at most two odd subcycles, and that the maximum genus of G（n, k） is more than 「β（G（n,k））/3」 in most cases.
Let G =（V（G）, E（G）） be a graph with vertex set V（G） and edge set E（G）. For two distinct vertices x and y of a graph G, let RG{x, y} denote the set of vertices z such that the distance from x to z is not equa...Let G =（V（G）, E（G）） be a graph with vertex set V（G） and edge set E（G）. For two distinct vertices x and y of a graph G, let RG{x, y} denote the set of vertices z such that the distance from x to z is not equa l to the distance from y to z in G. For a function g defined on V（G） and for U V（G）, let g（U） =∑s∈Ug（s）. A real-valued function g ： V（G） → [0, 1] is a resolving function of G if g（RG{x, y}） ≥ 1 for any two distinct vertices x, y ∈ V（G）. The fractional metric dimension dimf（G）of a graph G is min{g（V（G）） ： g is a resolving function of G}. Let G1 and G2 be disjoint copies of a graph G, and let σ ： V（G1） → V（G2） be a bijection. Then, a permutation graph Gσ =（V, E） has the vertex set V = V（G1） ∪ V（G2） and the edge set E = E（G1） ∪ E（G2） ∪ {uv ｜ v = σ（u）}. First,we determine dimf（T） for any tree T. We show that 1 〈 dimf（Gσ） ≤1/2（｜V（G）｜ ＋ ｜S（G）｜） for any connected graph G of order at least 3, where S（G） denotes the set of support vertices of G. We also show that, for any ε 〉 0, there exists a permutation graph Gσ such that dimf（Gσ）- 1 〈 ε. We give examples showing that neither is there a function h1 such that dimf（G） 〈 h1（dimf（Gσ）） for all pairs（G, σ）, nor is there a function h2 such that h2（dimf（G）） 〉 dimf（Gσ） for all pairs（G, σ）. Furthermore,we investigate dimf（Gσ） when G is a complete k-partite graph or a cycle.展开更多
The notion of super-edge-graceful graphs was introduced by Mitchem and Simoson in 1994.However, few examples except trees are known. In this paper, we exhibit two classes of infinitely many cubic graphs which are supe...The notion of super-edge-graceful graphs was introduced by Mitchem and Simoson in 1994.However, few examples except trees are known. In this paper, we exhibit two classes of infinitely many cubic graphs which are super-edge-graceful. A conjecture is proposed.展开更多
基金The NSF (10671073) of Chinathe Scientific Fund (03080045) of the Gathered Talents by Nantong UniversityNSF (07KJB110090) of Jiangsu University.
文摘In this paper we prove that the generalized permutation graph G（n, k） is upper embeddable if it has at most two odd subcycles, and that the maximum genus of G（n, k） is more than 「β（G（n,k））/3」 in most cases.
文摘Let G =（V（G）, E（G）） be a graph with vertex set V（G） and edge set E（G）. For two distinct vertices x and y of a graph G, let RG{x, y} denote the set of vertices z such that the distance from x to z is not equa l to the distance from y to z in G. For a function g defined on V（G） and for U V（G）, let g（U） =∑s∈Ug（s）. A real-valued function g ： V（G） → [0, 1] is a resolving function of G if g（RG{x, y}） ≥ 1 for any two distinct vertices x, y ∈ V（G）. The fractional metric dimension dimf（G）of a graph G is min{g（V（G）） ： g is a resolving function of G}. Let G1 and G2 be disjoint copies of a graph G, and let σ ： V（G1） → V（G2） be a bijection. Then, a permutation graph Gσ =（V, E） has the vertex set V = V（G1） ∪ V（G2） and the edge set E = E（G1） ∪ E（G2） ∪ {uv ｜ v = σ（u）}. First,we determine dimf（T） for any tree T. We show that 1 〈 dimf（Gσ） ≤1/2（｜V（G）｜ ＋ ｜S（G）｜） for any connected graph G of order at least 3, where S（G） denotes the set of support vertices of G. We also show that, for any ε 〉 0, there exists a permutation graph Gσ such that dimf（Gσ）- 1 〈 ε. We give examples showing that neither is there a function h1 such that dimf（G） 〈 h1（dimf（Gσ）） for all pairs（G, σ）, nor is there a function h2 such that h2（dimf（G）） 〉 dimf（Gσ） for all pairs（G, σ）. Furthermore,we investigate dimf（Gσ） when G is a complete k-partite graph or a cycle.
基金Partially supported by Faculty-Research Grant,Hong Kong Baptist University
文摘The notion of super-edge-graceful graphs was introduced by Mitchem and Simoson in 1994.However, few examples except trees are known. In this paper, we exhibit two classes of infinitely many cubic graphs which are super-edge-graceful. A conjecture is proposed.
