Hamilton decompositions of complete multipartite graphs with any 2-factor leave

For m ≥ 1 and p ≥ 2, given a set of integers s₁,…,s_q with for and , necessary and sufficient conditions are found for the existence of a hamilton decomposition of the complete p-partite graph , where U is a 2-factor of consisting of q cycles, the jth cycle having length s_j. This result is then used to completely solve the problem when p = 3, removing the condition that . © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 208–214, 2003     

Packing complete multipartite graphs with 4‐cycles

In this paper we completely solve the problem of finding a maximum packing of any complete multipartite graph with edge‐disjoint 4‐cycles, and the minimum leaves are explicitly given. © 2001 John Wiley & Sons, Inc. J Combin Designs 9: 107–127, 2001     

Maximal sets of hamilton cycles in complete multipartite graphs

A set S of edge‐disjoint hamilton cycles in a graph G is said to be maximal if the edges in the hamilton cycles in S induce a subgraph H of G such that G ? E(H) contains no hamilton cycles. In this context, the spectrum S(G) of a graph G is the set of integers m such that G contains a maximal set of m edge‐disjoint hamilton cycles. This spectrum has previously been determined for all complete graphs and for all complete bipartite graphs. In this paper, we extend these results to the complete multipartite graphs. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 49–66, 2003     

Decompositions of complete multipartite graphs

This paper answers a recent question of Dobson and Maruši? by partitioning the edge set of a complete bipartite graph into two parts, both of which are edge sets of arc-transitive graphs, one primitive and the other imprimitive. The first member of the infinite family is the one constructed by Dobson and Maruši?.     

On the seidel integral complete multipartite graphs

For a simple undirected graph G, denote by A(G) the (0,1)-adjacency matrix of G. Let thematrix S(G) = J-I-2A(G) be its Seidel matrix, and let S _G (??) = det(??I-S(G)) be its Seidel characteristic polynomial, where I is an identity matrix and J is a square matrix all of whose entries are equal to 1. If all eigenvalues of S _G (??) are integral, then the graph G is called S-integral. In this paper, our main goal is to investigate the eigenvalues of S _G (??) for the complete multipartite graphs G = $G = K_{n_1 ,n_2 ,...n_t } $ . A necessary and sufficient condition for the complete tripartite graphs K _m,n,t and the complete multipartite graphs to be S-integral is given, respectively.     

完全r部图Kr（t）的{=C3，C2k}-强制分解（k≥4）的渐近存在性

研究基于顶点集V=Ui=1^rVi（其中｜Vi｜=t，i=1，2，……，r）的完全r部图Kr（t）的3圈和2k圈{C3，C2k}-强制分解（k≥4）的存在性问题．通过构造并运用Kr（t）的两种分解法，证明了Kr（t）的〈C3，C2k}-强制分解（k≥4）的渐近存在性，即对于任意给定的正整数k≥4，存在常数r0（k）=5k＋2，使得当r≥r0（k）时，Kr（t）的{C3，C2k}-强制分解存在的必要条件也是充分的．     

Remarks on Q-integral complete multipartite graphs

A graph is Q-integral if the spectrum of its signless Laplacian matrix consists entirely of integers. In their study of Q-integral complete multipartite graphs, [Zhao et al., Q-integral complete r-partite graphs, Linear Algebra Appl. 438 (2013) 1067–1077] posed two questions on the existence of such graphs. We resolve these questions and present some further results characterizing particular classes of Q-integral complete multipartite graphs.     

Factorizations of complete multipartite graphs into generalized cubes

For a positive integer d, the usual d‐dimensional cube Q_d is defined to be the graph (K₂)^d, the Cartesian product of d copies of K₂. We define the generalized cube Q(K_k, d) to be the graph (K_k)^d for positive integers d and k. We investigate the decomposition of the complete multipartite graph K into factors that are vertex‐disjoint unions of generalized cubes Q(K_k, d_i), where k is a power of a prime, n and j are positive integers with j ≤ n, and the d_i may be different in different factors. We also use these results to partially settle a problem of Kotzig on Q_d‐factorizations of K_n. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 144–150, 2000     

Line graphs of complete multipartite graphs have small cycle double covers

It has been shown by MacGillivray and Seyffarth (Austral. J. Combin. 24 (2001) 91) that bridgeless line graphs of complete graphs, complete bipartite graphs, and planar graphs have small cycle double covers. In this paper, we extend the result for complete bipartite graphs, and show that the line graph of any complete multipartite graph (other than K_1,2) has a small cycle double cover.     

Bounded transversals in multipartite graphs

Transversals in r‐partite graphs with various properties are known to have many applications in graph theory and theoretical computer science. We investigate f‐bounded transversal s (or f‐BT), that is, transversals whose connected components have order at most f. In some sense we search for the sparsest f‐BT‐free graphs. We obtain estimates on the smallest maximum degree that 3‐partite and 4‐partite graphs without 2‐BT can have and provide a greatly simplified proof of the best known general lower bound on the smallest maximum degree in f‐BT‐free graphs. © 2011 Wiley Periodicals, Inc. J Graph Theory.     

Vertex coloring complete multipartite graphs from random lists of size 2

Let K_s×m be the complete multipartite graph with s parts and m vertices in each part. Assign to each vertex v of K_s×m a list L(v) of colors, by choosing each list uniformly at random from all 2-subsets of a color set C of size σ(m). In this paper we determine, for all fixed s and growing m, the asymptotic probability of the existence of a proper coloring φ, such that φ(v)∈L(v) for all v∈V(K_s×m). We show that this property exhibits a sharp threshold at σ(m)=2(s−1)m.     

Partitioning complete multipartite graphs by monochromatic trees

The tree partition number of an r‐edge‐colored graph G, denoted by t_r(G), is the minimum number k such that whenever the edges of G are colored with r colors, the vertices of G can be covered by at most k vertex‐disjoint monochromatic trees. We determine t₂(K(n₁, n₂,…, n_k)) of the complete k‐partite graph K(n₁, n₂,…, n_k). In particular, we prove that t₂(K(n, m)) = ? (m‐2)/2ⁿ? + 2, where 1 ≤ n ≤ m. © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 133–141, 2005     

Critical groups for complete multipartite graphs and Cartesian products of complete graphs

The critical group of a connected graph is a finite abelian group, whose order is the number of spanning trees in the graph, and which is closely related to the graph Laplacian. Its group structure has been determined for relatively few classes of graphs, e.g., complete graphs and complete bipartite graphs. For complete multipartite graphs , we describe the critical group structure completely. For Cartesian products of complete graphs , we generalize results of H. Bai on the k-dimensional cube, by bounding the number of invariant factors in the critical group, and describing completely its p-primary structure for all primes p that divide none of . © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 231–250, 2003     

Hamilton cycle rich two‐factorizations of complete graphs

For all integers n ≥ 5, it is shown that the graph obtained from the n‐cycle by joining vertices at distance 2 has a 2‐factorization is which one 2‐factor is a Hamilton cycle, and the other is isomorphic to any given 2‐regular graph of order n. This result is used to prove several results on 2‐factorizations of the complete graph K_n of order n. For example, it is shown that for all odd n ≥ 11, K_n has a 2‐factorization in which three of the 2‐factors are isomorphic to any three given 2‐regular graphs of order n, and the remaining 2‐factors are Hamilton cycles. For any two given 2‐regular graphs of even order n, the corresponding result is proved for the graph K_n ‐ I obtained from the complete graph by removing the edges of a 1‐factor. © 2004 Wiley Periodicals, Inc.     

Locally 2‐arc transitive graphs,homogeneous factorizations,and partial linear spaces

We establish natural bijections between three different classes of combinatorial objects; namely certain families of locally 2‐arc transitive graphs, partial linear spaces, and homogeneous factorizations of arc‐transitive graphs. Moreover, the bijections intertwine the actions of the relevant automorphism groups. Thus constructions in any of these areas provide examples for the others. © 2005 Wiley Periodicals, Inc. J Combin Designs 14: 139–148, 2006     

Partitioning edge-coloured complete graphs into monochromatic cycles

A conjecture of Erdös, Gyárfás, and Pyber says that in any edge-colouring of a complete graph with r colours, it is possible to cover all the vertices with r vertex-disjoint monochromatic cycles. So far, this conjecture has been proven only for $r=2$. In this note we show that in fact this conjecture is false for all $r⩾3$. We also discuss some weakenings of this conjecture which may still be true.     

Sparse pseudo‐random graphs are Hamiltonian

In this article we study Hamilton cycles in sparse pseudo‐random graphs. We prove that if the second largest absolute value λ of an eigenvalue of a d‐regular graph G on n vertices satisfies and n is large enough, then G is Hamiltonian. We also show how our main result can be used to prove that for every c >0 and large enough n a Cayley graph X (G,S), formed by choosing a set S of c log⁵ n random generators in a group G of order n, is almost surely Hamiltonian. © 2002 Wiley Periodicals, Inc. J Graph Theory 42: 17–33, 2003     

Archimedean ϕ ‐tolerance graphs

Let ? be a symmetric binary function, positive valued on positive arguments. A graph G = (V,E) is a ?‐tolerance graph if each vertex υ ∈ V can be assigned a closed interval I_υ and a positive tolerance t_υ so that xy ∈ E ? | I_x ∩ I_y|≥ ? (t_x,t_y). An Archimedean function has the property of tending to infinity whenever one of its arguments tends to infinity. Generalizing a known result of [15] for trees, we prove that every graph in a large class (which includes all chordless suns and cacti and the complete bipartite graphs K_2,k) is a ?‐tolerance graph for all Archimedean functions ?. This property does not hold for most graphs. Next, we present the result that every graph G can be represented as a ?_G‐tolerance graph for some Archimedean polynomial ?_G. Finally, we prove that there is a ?universal”? Archimedean function ? ^* such that every graph G is a ?^*‐tolerance graph. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 179–194, 2002