On the Ascending Subgraph Decompositions Problem

Inthispaper,weconsideronlysimpleundirectedgraphsandfollowBondyandMurtyl7]forterminologyandnotationnotdefinedhere.Y.Alaviandothershavegiventhedefinitionoftheascendingsubgraphdecomposionin[1].LetGbeagraphofqedgessatisfy( 1)5q<( ,).ThenGissaidtohavean...     

Decompositions of Complete Graphs

If s₁, s₂, ..., s_t are integers such that n – 1 = s₁ +s₂ + ... + s_t and such that for each i (1 i t), 2 s_i n –1 and s_in is even, then K_n can be expressed as the union G₁G₂...G_tof t edge-disjoint factors, where for each i, G_i is s_i-regularand s_i-connected. Moreover, whenever s_i = s_j, G_i and G_j areisomorphic. 1991 Mathematics Subject Classification 05C70.     

几类可升分解的图

Ａｌａｖｉ等人在文献［１］中定义了图的一种新分解，即“升分解”，并且猜想：任意有正数条边的图都可升分解。本文证明了下面三类图可升分解，并得到了一些有意义的推论。１设Ｒｎ是一个至多含有ｎ个顶点和至多含有ｎ条边的图，Ｋｎ－Ｒｎ可升分解（ｎ≥５）；２对称图可升分解；３对称图Ｇ的混合积（Ｇ；ｋ）可升分解。     

Chaotic Numbers of Complete Bipartite Graphs and Tripartite Graphs

In this paper, we study the chaotic numbers of complete bipartite graphs and complete tripartite graphs. For the complete bipartite graphs, we find closed-form formulas of the chaotic numbers and characterize all chaotic mappings. For the complete tripartite graphs, we develop an algorithm running in O(n ⁴ ₃) time to find the chaotic numbers, with n ₃ the number of vertices in the largest partite set.Research supported by NSC 90-2115-M-036-003.The author thanks the authors of Ref. 6, since his work was motivated by their work. Also, the author thanks the referees for helpful comments which made the paper more readable.     

Petersen Graph Decompositions of Complete Multipartite Graphs

Let P be the Petersen graph, and K _u(h) the complete multipartite graph with u parts of size h. A decomposition of K _u(h) into edge-disjoint copies of the Petersen graph P is called a P-decomposition of K _u(h) or a P-group divisible design of type h ^u . In this paper, we show that there exists a P-decomposition of K _u(h) if and only if h²u(u-1) o 0 mod 30{h^2u(u-1)\equiv 0 \pmod {30}} , h(u-1) o 0 mod 3{h(u-1)\equiv 0\pmod 3} , and u ≥ 3 with a definite exception (h, u) = (1, 10).     

Dihedral Biembeddings and Triangulations by Complete and Complete Tripartite Graphs

We construct biembeddings of some Latin squares which are Cayley tables of dihedral groups. These facilitate the construction of ${n^{an^2}}$ nonisomorphic face 2-colourable triangular embeddings of the complete tripartite graph K _n,n,n and the complete graph K _n for linear classes of values of n and suitable constants a. Previously the best known lower bounds for the number of such embeddings that are applicable to linear classes of values of n were of the form ${2^{an^2}.}$ We remark that trivial upper bounds are ${n^{n^2/3}}$ in the case of complete graphs K _n and ${n^{2n^2}}$ in the case of complete tripartite graphs K _n,n,n .     

Rank 3 Transitive Decompositions of Complete Multipartite Graphs

A transitive decomposition of a graph is a partition of the edge or arc set giving a set of subgraphs which are preserved and permuted transitively by a group of automorphisms of the graph. This paper deals with transitive decompositions of complete multipartite graphs preserved by an imprimitive rank 3 permutation group. We obtain a near-complete classification of these when the group in question has an almost simple component.     

一类完全三部图的色唯一性

用P(G,λ)表示简单图G的色多项式.设G是一个给定的简单图,若对任意简单图H,当P(H,λ)=P(G,λ)时都有H和G同构(记为H≌G),则称图G是色唯一的.本文证明了以下结果:设n,k,△都为非负整数,其中k≥0,△∈{4,5},若n≥1/3k~2+1/3△~2-1/3k△-1/3k-1/3△+4/3,则完全三部图K(n,n+△,n+k)是色唯一的.同时还给出了一个猜想.     

若干完全三部图的色唯一性

用P(G,λ)表示图G的色多项式.若对任意图H,当P(H,λ)=P(G,λ)时都有H和G同构,则称图G是色唯一的.给出了以下结果:m≥2且k≥0时,完全三部图K(m,m,m+k)是色唯一的;m≥2且m+1>k≥0时,完全三部图K(m,m+1,m+k)是色唯一的.     

Decompositions of Complete Multipartite Graphs into Cycles of Even Length

Necessary and sufficient conditions for the existence of an edge-disjoint decomposition of any complete multipartite graph into even length cycles are investigated. Necessary conditions are listed and sufficiency is shown for the cases when the cycle length is 4, 6 or 8. Further results concerning sufficiency, provided certain “small” decompositions exist, are also given for arbitrary even cycle lengths. Revised: November 28, 1997     

Subgraph Transversal of Graphs

Given graphs F and G, denote by \({\tau_F}(G)\) the cardinality of a smallest subset \(T {\subseteq}V(G)\) that meets every maximal F-free subgraph of G. Erdös, Gallai and Tuza [9] considered the question of bounding \(\tau_{\overline{K_2}}(G)\) by a constant fraction of |G|. In this paper, we will give a complete answer to the following question: for which F, is τ _F (G) bounded by a constant fraction of |G|?In addition, for those graphs F for which \({\tau_F}(G)\) is not bounded by any fraction of |G|, we prove that \(\tau_F(G)\le|G|-\frac{1}{2}\sqrt{|G|}+\frac{1}{2}\), provided F is not K _k or \(\overline{K_k}\).     

6个素数阶完全图的循环图分解

研究素数阶完全图分解为循环图的方法 ,给出计算它的子图的团数的一种算法 ,得到 3个三色 ,3个四色 Ramsey数的新的下界 :R(3,3,13) 194 ,R(3,4 ,11) 2 12 ,R(3,6 ,13) 52 2 ,R(3,3,4 ,10 ) 380 ,R(3,3,6 ,14) 1154,R(3,4 ,5,13) 10 94     

On the Ascending Subgraph Decomposition Problem

§１．　ＩｎｔｒｏｄｕｃｔｉｏｎＩｎｐａｐｅｒ［１］,Ａｌａｖｉａｎｄｏｔｈｅｒｓｄｅｆｉｎｅｄｔｈｅｃｏｎｃｅｐｔｏｆａｓｃｅｎｄｉｎｇｓｕｂｇｒａｐｈｄｅｃｏｍｐｏｓｉｔｉｏｎ：Ｄｅｆｉｎｉｔｉｏｎ　ＬｅｔＧｂｅａｇｒａｐｈｏｆｐｏｓｉｔｉｖｅｓｉｚｅｑ,ａｎｄｌｅｔｎｂｅｔｈａｔｐｏｓｉｔｉｖｅｉｎｔｅｇｅｒｆｏｒｗｈｉｃｈｎ＋１２ｑ＜ｎ＋２２．ＴｈｅｎＧｉｓｓａｉｄｔｏｈａｖｅａｎａｓｃｅｎｄｉｎｇｓｕｂｇｒａｐｈｄｅｃｏｍｐｏｓｉｔｉｏｎ（ＡＳＤ）ｉｆＧｃａｎｂｅｄｅｃｏｍｐｏｓｅｄ…     

k-Factors and Spanning Subgraph in Graphs

In this paper, we discussed k-factors and spanning subgraph, and propose a conjecture which will lead to a series of important conclusion.     

Large Sets of Hamilton Cycle and Path Decompositions of Complete Bipartite Graphs

In this paper, we determine the existence spectrums for large sets of Hamilton cycle and path (resp. directed Hamilton cycle and path) decompositions of ??K _{m, n} (resp. ${\lambda K^{*}_{m,n}}$ ).     

关于图的升分解的Alavi猜想

Y.Alavi等人在1987年定义了图的一种新分解,即“升分解”(ascebding subgraph decomposition),并提出猜想:设自然数n≥2,G是由k个分离的星S_1,S_2,…,S_k构成的图,S_i含有a_i条边,n≤a_i≤2n-2,,则G可升分解为星的并。本文证明了当n=2k+i(i=0,1,2)时猜想成立。