Cycle multiplicity of a graph G is the maximum number of edge disjoint cycles in G. In this paper, we determine the cycle multiplicity of and then obtain the formula of cycle multiplicity of total graph of complete bi...Cycle multiplicity of a graph G is the maximum number of edge disjoint cycles in G. In this paper, we determine the cycle multiplicity of and then obtain the formula of cycle multiplicity of total graph of complete bipartite graph, this generalizes the result for, which is given by M.M. Akbar Ali in [1].展开更多
The well known Zarankiewicz' conjecture is said that the crossing number of the complete bipartite graph Km,n (m≤n) is Z(m,n). where Z(m,n) = [m/2] [(m-1)/2] [n/2] [(n-1)/2](for and real number x, [x] denotes the...The well known Zarankiewicz' conjecture is said that the crossing number of the complete bipartite graph Km,n (m≤n) is Z(m,n). where Z(m,n) = [m/2] [(m-1)/2] [n/2] [(n-1)/2](for and real number x, [x] denotes the maximal integer no more than x). Presently, Zarankiewicz' conjecture is proved true only for the case m≤G. In this article, the authors prove that if Zarankiewicz' conjecture holds for m≤9, then the crossing number of the complete tripartite graph K1,8,n is Z(9, n) + 12[n/2].展开更多
<div style="text-align:justify;"> <span style="font-family:Verdana;">In the field of design theory, the most well-known design is a Steiner Triple System. In general, a G-design on H is...<div style="text-align:justify;"> <span style="font-family:Verdana;">In the field of design theory, the most well-known design is a Steiner Triple System. In general, a G-design on H is an edge-disjoint decomposition of H into isomorphic copies of G. In a Steiner Triple system, a complete graph is decomposed into triangles. In this paper we let H be a complete graph with a hole and G be a complete graph on four vertices minus one edge, also referred to as a <img alt="" src="Edit_e69ee166-4bbc-48f5-8ba1-b446e7d3738c.png" /> . A complete graph with a hole, <img alt="" src="Edit_558c249b-55e8-4f3b-a043-e36d001c4250.png" />, consists of a complete graph on <em>d</em> vertices, <img alt="" src="Edit_cb1772f7-837c-4aea-b4a6-cb38565f5a8b.png" />, and a set of independent vertices of size<em> v, V,</em> where each vertex in <em>V</em> is adjacent to each vertex in <img alt="" src="Edit_cb1772f7-837c-4aea-b4a6-cb38565f5a8b.png" />. When <em>d</em> is even, we give two constructions for the decomposition of a complete graph with a hole into copies of <img alt="" src="Edit_e69ee166-4bbc-48f5-8ba1-b446e7d3738c.png" /> : the Alpha-Delta Construction, and the Alpha-Beta-Delta Construction. By restricting <em>d</em> and <em>v</em> so that <img alt="" src="Edit_6bb9e3b4-1769-4b28-bf89-bc97c47c637e.png" /><span style="white-space:nowrap;"> </span>, we are able to resolve both of these cases for a subset of <img alt="" src="Edit_558c249b-55e8-4f3b-a043-e36d001c4250.png" />using difference methods and 1-factors.</span> </div>展开更多
In this paper,a new concept of an optimal complete multipartite decomposition of type 1 (type 2) of a complete n-partite graph Q n is proposed and another new concept of a normal complete multipartite decomposition o...In this paper,a new concept of an optimal complete multipartite decomposition of type 1 (type 2) of a complete n-partite graph Q n is proposed and another new concept of a normal complete multipartite decomposition of K n is introduced.It is showed that an optimal complete multipartite decomposition of type 1 of K n is a normal complete multipartite decomposition.As for any complete multipartite decomposition of K n,there is a derived complete multipartite decomposition for Q n.It is also showed that any optimal complete multipartite decomposition of type 1 of Q n is a derived decomposition of an optimal complete multipartite decomposition of type 1 of K n.Besides,some structural properties of an optimal complete multipartite decomposition of type 1 of K n are given.展开更多
Let P（G,A） be the chromatic polynomial of a graph G. A graph G is chromatically unique if for any graph H, P（H, λ） = P（G, λ） implies H is isomorphic to G. Liu et al. [Liu, R. Y., Zhao, H. X., Ye, C. F.： A com...Let P（G,A） be the chromatic polynomial of a graph G. A graph G is chromatically unique if for any graph H, P（H, λ） = P（G, λ） implies H is isomorphic to G. Liu et al. [Liu, R. Y., Zhao, H. X., Ye, C. F.： A complete solution to a conjecture on chromatic uniqueness of complete tripartite graphs. Discrete Math., 289, 175 179 （2004）], and Lau and Peng [Lau, G. C., Peng, Y. H.： Chromatic uniqueness of certain complete t-partite graphs. Ars Comb., 92, 353-376 （2009）] show that K（p - k,p - i,p） for i = 0, 1 are chromatically unique if p ≥ k ＋ 2 ≥ 4. In this paper, we show that if 2 〈 i 〈 4, the complete tripartite graph K（p - k,p - i,p） is chromatically unique for integers k ≥ i and p 〉 k2/4 ＋ i ＋ 1.展开更多
Let P（G,λ） be the chromatic polynomial of a simple graph G. A graph G is chromatically unique if for any simple graph H, P（H,λ） = P（G,λ） implies that H is isomorphic to G. Many sufficient conditions guarantee...Let P（G,λ） be the chromatic polynomial of a simple graph G. A graph G is chromatically unique if for any simple graph H, P（H,λ） = P（G,λ） implies that H is isomorphic to G. Many sufficient conditions guaranteeing that some certain complete tripartite graphs are chromatically unique were obtained by many scholars. Especially, in 2003, Zou Hui-wen showed that if n 〉 1/3m2 ＋ 3/1k2 ＋ 3/1mk＋ 1/3m-1/3k＋ 3/2√m2 ＋ k2 ＋ mk, where n,k and m are non-negative integers, then the complete tripartite graph K（n - m,n,n ＋ k） is chromatically unique （or simply χ–unique）. In this paper, we prove that for any non-negative integers n,m and k, where m ≥ 2 and k ≥ 0, if n ≥ 3/1m2 ＋ 3/1k2 ＋ 3/1mk ＋ 3/1m - 3/1k ＋ 43, then the complete tripartite graph K（n - m,n,n ＋ k） is χ–unique, which is an improvement on Zou Hui-wen’s result in the case m ≥ 2 and k ≥ 0. Furthermore, we present a related conjecture.展开更多
图 G 的全部的色彩的数字 T (G) 是需要渲染 G 的元素(顶点和边) 的颜色的最小的数字以便不邻近或元素的事件对收到一样的颜色。G 被称为类型 1 如果 T (G)=(G)+ 1。在这份报纸，我们证明完全的由两部组成的图 Km， n 和周期 Cn 的 join...图 G 的全部的色彩的数字 T (G) 是需要渲染 G 的元素(顶点和边) 的颜色的最小的数字以便不邻近或元素的事件对收到一样的颜色。G 被称为类型 1 如果 T (G)=(G)+ 1。在这份报纸，我们证明完全的由两部组成的图 Km， n 和周期 Cn 的 join 具有类型 1。展开更多
A necessary and sufficient condition is given for a doubly nonnegative matrix realization of a cycle to be completely positive. Also some special non-CP graphs are investigated.
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.展开更多
文摘Cycle multiplicity of a graph G is the maximum number of edge disjoint cycles in G. In this paper, we determine the cycle multiplicity of and then obtain the formula of cycle multiplicity of total graph of complete bipartite graph, this generalizes the result for, which is given by M.M. Akbar Ali in [1].
基金This work is supported by the Key Project of the Education Department of Hunan Province of China (05A037)by Scientific Research Fund of Hunan Provincial Education Department (06C515).
文摘The well known Zarankiewicz' conjecture is said that the crossing number of the complete bipartite graph Km,n (m≤n) is Z(m,n). where Z(m,n) = [m/2] [(m-1)/2] [n/2] [(n-1)/2](for and real number x, [x] denotes the maximal integer no more than x). Presently, Zarankiewicz' conjecture is proved true only for the case m≤G. In this article, the authors prove that if Zarankiewicz' conjecture holds for m≤9, then the crossing number of the complete tripartite graph K1,8,n is Z(9, n) + 12[n/2].
文摘<div style="text-align:justify;"> <span style="font-family:Verdana;">In the field of design theory, the most well-known design is a Steiner Triple System. In general, a G-design on H is an edge-disjoint decomposition of H into isomorphic copies of G. In a Steiner Triple system, a complete graph is decomposed into triangles. In this paper we let H be a complete graph with a hole and G be a complete graph on four vertices minus one edge, also referred to as a <img alt="" src="Edit_e69ee166-4bbc-48f5-8ba1-b446e7d3738c.png" /> . A complete graph with a hole, <img alt="" src="Edit_558c249b-55e8-4f3b-a043-e36d001c4250.png" />, consists of a complete graph on <em>d</em> vertices, <img alt="" src="Edit_cb1772f7-837c-4aea-b4a6-cb38565f5a8b.png" />, and a set of independent vertices of size<em> v, V,</em> where each vertex in <em>V</em> is adjacent to each vertex in <img alt="" src="Edit_cb1772f7-837c-4aea-b4a6-cb38565f5a8b.png" />. When <em>d</em> is even, we give two constructions for the decomposition of a complete graph with a hole into copies of <img alt="" src="Edit_e69ee166-4bbc-48f5-8ba1-b446e7d3738c.png" /> : the Alpha-Delta Construction, and the Alpha-Beta-Delta Construction. By restricting <em>d</em> and <em>v</em> so that <img alt="" src="Edit_6bb9e3b4-1769-4b28-bf89-bc97c47c637e.png" /><span style="white-space:nowrap;"> </span>, we are able to resolve both of these cases for a subset of <img alt="" src="Edit_558c249b-55e8-4f3b-a043-e36d001c4250.png" />using difference methods and 1-factors.</span> </div>
基金Supported by the National Natural Science Foundation of China( 1 0 2 71 1 1 0 )
文摘In this paper,a new concept of an optimal complete multipartite decomposition of type 1 (type 2) of a complete n-partite graph Q n is proposed and another new concept of a normal complete multipartite decomposition of K n is introduced.It is showed that an optimal complete multipartite decomposition of type 1 of K n is a normal complete multipartite decomposition.As for any complete multipartite decomposition of K n,there is a derived complete multipartite decomposition for Q n.It is also showed that any optimal complete multipartite decomposition of type 1 of Q n is a derived decomposition of an optimal complete multipartite decomposition of type 1 of K n.Besides,some structural properties of an optimal complete multipartite decomposition of type 1 of K n are given.
文摘Let P（G,A） be the chromatic polynomial of a graph G. A graph G is chromatically unique if for any graph H, P（H, λ） = P（G, λ） implies H is isomorphic to G. Liu et al. [Liu, R. Y., Zhao, H. X., Ye, C. F.： A complete solution to a conjecture on chromatic uniqueness of complete tripartite graphs. Discrete Math., 289, 175 179 （2004）], and Lau and Peng [Lau, G. C., Peng, Y. H.： Chromatic uniqueness of certain complete t-partite graphs. Ars Comb., 92, 353-376 （2009）] show that K（p - k,p - i,p） for i = 0, 1 are chromatically unique if p ≥ k ＋ 2 ≥ 4. In this paper, we show that if 2 〈 i 〈 4, the complete tripartite graph K（p - k,p - i,p） is chromatically unique for integers k ≥ i and p 〉 k2/4 ＋ i ＋ 1.
基金Supported by the National Natural Science Foundation of China (Grant No.10771091)the Science and Research Project of the Education Department of Gansu Province (Grant No.0501-02)
文摘Let P（G,λ） be the chromatic polynomial of a simple graph G. A graph G is chromatically unique if for any simple graph H, P（H,λ） = P（G,λ） implies that H is isomorphic to G. Many sufficient conditions guaranteeing that some certain complete tripartite graphs are chromatically unique were obtained by many scholars. Especially, in 2003, Zou Hui-wen showed that if n 〉 1/3m2 ＋ 3/1k2 ＋ 3/1mk＋ 1/3m-1/3k＋ 3/2√m2 ＋ k2 ＋ mk, where n,k and m are non-negative integers, then the complete tripartite graph K（n - m,n,n ＋ k） is chromatically unique （or simply χ–unique）. In this paper, we prove that for any non-negative integers n,m and k, where m ≥ 2 and k ≥ 0, if n ≥ 3/1m2 ＋ 3/1k2 ＋ 3/1mk ＋ 3/1m - 3/1k ＋ 43, then the complete tripartite graph K（n - m,n,n ＋ k） is χ–unique, which is an improvement on Zou Hui-wen’s result in the case m ≥ 2 and k ≥ 0. Furthermore, we present a related conjecture.
基金This research is supported by the Education Committee of Anhui Province.
文摘A necessary and sufficient condition is given for a doubly nonnegative matrix realization of a cycle to be completely positive. Also some special non-CP graphs are investigated.
文摘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.
