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.     

完全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}-强制分解存在的必要条件也是充分的．     

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.     

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     

完全六部图是S-整图的一个充要条件

在他人研究完全多部图的邻接谱的基础上,对整完全多部图的Seidel多项式进行研究分析,以期得到完全六部图G是S-整图的充要条件．从讨论完全六部图的Seidel多项式入手,应用矩阵行初等变换的方法给出完全六部图G是S-整图的充要条件．     

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?.     

Nondisconnecting disentanglements of amalgamated 2‐factorizations of complete multipartite graphs

In this paper necessary and sufficient conditions are found for an edge‐colored graph H to be the homomorphic image of a 2‐factorization of a complete multipartite graph G in which each 2‐factor of G has the same number of components as its corresponding color class in H. This result is used to completely solve the problem of finding hamilton decompositions of K_a,b ? E(U) for any 2‐factor U of K_a,b. © 2001 John Wiley & Sons, Inc. J Combin Designs 9: 460–467, 2001     

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     

完全五部图的S-整图性研究

应用矩阵的初等变换得到了完全五部图的 Seidel 多项式,并给出了完全五部图是S-整图的一个充分必要条件。进一步刻画了完全正则五部图和两类特殊完全五部图的Seidel谱。     

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     

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     

Cyclic cycle systems of the complete multipartite graph

In this paper, we study the existence problem for cyclic $?$‐cycle decompositions of the graph $K_m\left[n\right]$, the complete multipartite graph with $m$ parts of size $n$, and give necessary and sufficient conditions for their existence in the case that $2?|\left(m?1\right)n$.     

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.     

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     

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.     

Closed trail decompositions of complete equipartite graphs

The complete equipartite graph $K_m * {\overline{K_n}}$ has mn vertices partitioned into m parts of size n, with two vertices adjacent if and only if they are in different parts. In this paper, we determine necessary and sufficient conditions for the existence of a decomposition of $K_m * {\overline{K_n}}$ into closed trails of length k. © 2009 Wiley Periodicals, Inc. J Combin Designs 17: 374–403, 2009     

On complete graphs with negative r-mean curvature

We generalize Efimov's Theorem for graphs in Euclidean space using the scalar curvature, with an additional hypothesis on the second fundamental form.     

Random walks systems on complete graphs

We study two versions of random walks systems on complete graphs. In the first one, the random walks have geometrically distributed lifetimes so we define and identify a non-trivial critical parameter related to the proportion of visited vertices before the process dies out. In the second version, the lifetimes depend on the past of the process in a non-Markovian setup. For that version, we present results obtained from computational analysis, simulations and a mean field approximation. These three approaches match.