Long Snakes in Powers of the Complete Graph with an Odd Number of Vertices

In [5] Abbott and Katchalski ask if there exists a constantc < 0 such that for every d 2 there is a snake (cycle withoutchords) of length at least c3^d in the product of d copies ofthe complete graph K₃. We show that the answer to the abovequestion is positive, and that in general for any odd integern there is a constant c_n such that for every d 2 there is asnake of length at least c_n n^d in the product of d copies ofthe complete graph K_n.     

On the Decomposition of Graphs into Complete Bipartite Graphs

In a complete bipartite decomposition π of a graph, we consider the number ϑ(v;π) of complete bipartite subgraphs incident with a vertex v. Let ϑ(G)= ϑ(v;π). In this paper the exact values of ϑ(G) for complete graphs and hypercubes and a sharp upper bound on ϑ(G) for planar graphs are provided, respectively. An open problem proposed by P.C. Fishburn and P.L. Hammer is solved as well.     

An Upper Bound on the Basis Number of the Powers of the Complete Graphs

The basis number of a graph G is defined by Schmeichel to be the least integer h such that G has an h-fold basis for its cycle space. MacLane showed that a graph is planar if and only if its basis number is . Schmeichel proved that the basis number of the complete graph K _n is at most 3>. We generalize the result of Schmeichel by showing that the basis number of the d-th power of K _n is at most 2d+1.     

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     

Decomposing Complete Equipartite Graphs into Closed Trails of Length k

Necessary conditions for a simple connected graph G to admit a decomposition into closed trails of length k ≥ 3 are that G is even and its total number of edges is a multiple of k. In this paper we show that these conditions are sufficient in the case when G is the complete equipartite graph having at least three parts, each of the same size.     

关于完全t部图的色唯一性

设P(G,λ)是图的色多项式。如果对任意使P(G,λ)=P(H,λ)的图H都与G同构,则称图G是色唯一图.这里通过比较t 1色类的色划分数目,讨论了由Koh和Teo在文献[1]中提出的问题(若|ni-nj|≤2,当min(n1,n2,…,nt)充分大时,完全t部图K(n1,n2,…,nt)是否是色唯一图?)。改进了文献[5]中的结果。证明了若Σ1≤i≤ta2i=T,min{n a1,n a2,…,nt at,n-1}≥(T 1)/2,则K(n a1,n a2,…,n at)是色唯一图(其中ai是实数,n ai是正整数)。从而证明了若|ni-nj|≤k(i,j=1,2,…,t),min{n1,n2,…,nt}≥tk2/8 1,则K(n1,n2,…,nt)是色唯一图。     

On Cyclic Decompositions of Complete Graphs into Tripartite Graphs

We introduce two new labelings for tripartite graphs and show that if a graph G with n edges admits either of these labelings, then there exists a cyclic G‐decomposition of for every positive integer x. We also show that if G is the union of two vertext‐disjoint cycles of odd length, other than , then G admits one of these labelings.     

On a Decomposition of Complete Graphs

It is shown, among other results, that for any prime power q, the complete graph on 1+q+q ²+q ³ vertices can be decomposed into a union of 1+q Siamese Strongly Regular Graphs S R G(1+q+q ²+q ³,q+q ²,q–1,q+1) sharing 1+q ² cliques of size 1+q. Acknowledgments.The authors are indebted to a referee for a very extensive report and for many suggestions which improved the presentation of the paper tremendously.AMS Subject Numbers: 05B05, 05B20, 05E30This work was completed while the first author was on sabbatical leave visiting Institute for studies in theoretical Physics and Mathematics, (IPM), in Tehran, Iran. Support and hospitality is appreciated. Supported by an NSERC operating grant.     

关于完全t部图K(n1,n2,…,nt)的色唯一性

设P（G，λ）是图G的色多项式，如果对任意使P（G，λ）=P（H，λ）的图H都与G同构，则称G是色唯一图。这里通过比较图的特征子图的个数，讨论了由Koh和Teo在文献[1]中提出的问题（若｜ni-nj｜≤2，1≤i，j≤t且min{n1，n2，…，nt}充分大，K（n1，n2，…，nt）是否为色唯一图？）。证明了，若｜ni—nj｜≤2且t↑∑↑i=1 ni〉t^2/2＋t√t-1，则K（n1，n2，…，nt）是色唯一图；若αi=0或k，t↑∑↑i=1 n＋αi〉t^2k^2/8＋｜tk｜/2√t-1，则K（n＋α1，n＋α2，…，n＋αt）是色唯一图。其条件比文献[4]中的条件较好一些。     

Decomposition of Complete Graphs into Isomorphic Complete Bipartite Graphs

A decomposition of a complete graph into disjoint copies of a complete bipartite graph is called a ‐design of order n. The existence problem of ‐designs has been completely solved for the graphs for , for , K_{2, 3} and K_{3, 3}. In this paper, I prove that for all , if there exists a ‐design of order N, then there exists a ‐design of order n for all (mod ) and . Giving necessary direct constructions, I provide an almost complete solution for the existence problem for complete bipartite graphs with fewer than 18 edges, leaving five orders in total unsolved.     

On Crossing Numbers of Complete Tripartite and Balanced Complete Multipartite Graphs

The crossing number cr(G) of a graph G is the minimum number of crossings in a drawing of G in the plane with no more than two edges intersecting at any point that is not a vertex. The rectilinear crossing number of G is the minimum number of crossings in a such drawing of G with edges as straight line segments. Zarankiewicz proved in 1952 that . We generalize the upper bound to and prove . We also show that for n large enough, and , with the tighter rectilinear lower bound established through the use of flag algebras. A complete multipartite graph is balanced if the partite sets all have the same cardinality. We study asymptotic behavior of the crossing number of the balanced complete r‐partite graph. Richter and Thomassen proved in 1997 that the limit as of over the maximum number of crossings in a drawing of exists and is at most . We define and show that for a fixed r and the balanced complete r‐partite graph, is an upper bound to the limit superior of the crossing number divided by the maximum number of crossings in a drawing.     

On the Number of Genus Embeddings of Complete Bipartite Graphs

In this paper, on the basis of joint tree model introduced by Liu, by dividing the associated surfaces into segments layer by layer, we show that there are at least ${C_{1}\cdot C_{2}^{\frac{m}{2}}\cdot C_{3}^{\frac{n}{2}}(m-1)^{m-\frac{1}{2}}(n-1)^{n-\frac{1}{2}}}$ distinct genus embeddings for complete bipartite graph K _m,n , where C ₁, C ₂, and C ₃ are constants depending on the residual class of m modular 4 and that of n modular 4.     

On Idomatic Partitions of Direct Products of Complete Graphs

Independent dominating sets in the direct product of four complete graphs are considered. Possible types of such sets are classified. The sets in which every pair of vertices agree in exactly one coordinate, called T ₁-sets, are explicitly described. It is proved that the direct product of four complete graphs admits an idomatic partition into T ₁-sets if and only if each factor has at least three vertices and the orders of at least two factors are divisible by 3.     

Families of Graphs Closed Under Taking Powers

 This paper gives simple proofs for “G ^k ∈? implies G ^{k +1}∈?” when ? is the family of all interval graphs, all proper interval graphs, all cocomparability graphs, or all m-trapezoid graphs. Received: November 21, 1997 Final version received: October 5, 1998     

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.     

完全多部图与完全图Kronercker积的点参数研究

若G1和G2是两个图,G1和G2的Kronecker图定义为V (G1×G2)= V (G1) × V (G2 E(G1 × G2)= {(u1,v1)(u2,v2)。在本文中,我们计算了p-部完全图 m1,m2,...,mp 和完全图Kn 的Kronecker积的顶点参数,m1 ≤ m2 ≤ ... ≤ mp,2 ≤ p ≤ n, and n ≥ 3 ,扩展了Mamut和Vumar的相关结论[Inform. Process. Lett. 106(2008)258-262].     

Common Multiples of Complete Graphs

A graph H is said to divide a graph G if there exists a setS of subgraphs of G, all isomorphic to H, such that the edgeset of G is partitioned by the edge sets of the subgraphs inS. Thus, a graph G is a common multiple of two graphs if eachof the two graphs divides G. This paper considers common multiples of a complete graph oforder m and a complete graph of order n. The complete graphof order n is denoted K_n. In particular, for all positive integersn, the set of integers q for which there exists a common multipleof K₃ and K_n having precisely q edges is determined. It is shown that there exists a common multiple of K₃ and K_nhaving q edges if and only if q 0 (mod 3), q 0 (mod n2) and (1) q 3 n2 when n 5 (mod 6); (2) q (n + 1) n2 when n is even; (3) q {36, 42, 48} when n = 4. The proof of this result uses a variety of techniques includingthe use of Johnson graphs, Skolem and Langford sequences, andequitable partial Steiner triple systems. 2000 MathematicalSubject Classification: 05C70, 05B30, 05B07.     

完全图的素圈因子分解

图的因子理论是图论研究中最活跃的课题之一.其中心问题是把一个图分解成具有给定性质的因子.