Regular embeddings of complete multipartite graphs

In this paper, we classify all regular embeddings of the complete multipartite graphs K_p,…,p for a prime p into orientable surfaces. Also, the same work is done for the regular embeddings of the lexicographical product of any connected arc-transitive graph of prime order q with the complement of the complete graph of prime order p, where q and p are not necessarily distinct. Lots of regular maps found in this paper are Cayley maps.     

Self-dual embeddings of complete multipartite graphs

In this paper we examine self-dual embeddings of complete multipartite graphs, focusing primarily on K_m(n) having m parts each of size n. If m = 2, then n must be even. If the embedding is on an orientable surface, then an Euler characteristic argument shows that no such embedding exists when n is odd and m ? 2, 3 (mod 4); there is no such restriction for embeddings on nonorientable surfaces. We show that these embeddings exist with a few small exceptions. As a corollary, every group has a Cayley graph with a self-dual embedding. Our main technique is an addition construction that combines self-dual embeddings of two subgraphs into a self-dual embedding of their union. We also apply this technique to nonregular multipartite graphs and to cubes.     

Integral complete multipartite graphs

A graph is called integral if all eigenvalues of its adjacency matrix are integers. In this paper, we investigate integral complete r-partite graphs K_p1,p2,…,pr=K_{a1·p1,a2·p2,…,as·ps} with s=3,4. We can construct infinite many new classes of such integral graphs by solving some certain Diophantine equations. These results are different from those in the existing literature. For s=4, we give a positive answer to a question of Wang et al. [Integral complete r-partite graphs, Discrete Math. 283 (2004) 231-241]. The problem of the existence of integral complete multipartite graphs K_{a1·p1,a2·p2,…,as·ps} with arbitrarily large number s remains open.     

Orientably-regular embeddings of a class of multipartite graphs

The orientably-regular embeddings of complete multipartite graphs have been determined by the contributions of several papers. After that, a natural question can be asked: How about the regular embeddings of the multipartite graphs with m parts, while each part contains n vertices(not necessarily complete multipartite). In this paper, we classify all the orientably-regular embeddings of these graphs when m is a prime q and n is a prime power pe.     

Eigenvalues of complete multipartite graphs

We compute the eigenvalues of the complete multipartite graph and present some applications of our result.     

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

Remarks on D-integral complete multipartite graphs

A graph is called distance integral (or D-integral) if all eigenvalues of its distance matrix are integers. In their study of D-integral complete multipartite graphs, Yang and Wang (2015) posed two questions on the existence of such graphs. We resolve these questions and present some further results on D-integral complete multipartite graphs. We give the first known distance integral complete multipartite graphs \({K_{{p_1},{p_2},{p_3}}}\) with p₁ < p₂ < p₃, and \({K_{{p_1},{p_2},{p_3},{p_4}}}\) with p₁ < p₂ < p₃ < p₄, as well as the infinite classes of distance integral complete multipartite graphs \({K_{{a_1}{p_1},{a_2}{p_2},...,{a_s}{p_s}}}\) with s = 5, 6.     

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     

The chromatic index of complete multipartite graphs

We show that a complete multipartite graph is class one if and only if it is not eoverfull, thus determining its chromatic index.     

P 3-factorization of complete multipartite graphs

In this paper, it is shown that a necessary and sufficient condition for the existence of aP ₃-factorization ofK _m ⁿ is (i)mn 0(mod 3) and (ii) (m – 1)n 0(mod 4).     

P 3-factorization of complete multipartite graphs

In this note it is shown that a necessary and sufficient condition for the existence of a P3-factorizatlon of complete multipartite graph λK, is (1) m≥3, (2) mn≡0(mod 3) and (3)λ(m-1)n≡0(mod 4).     

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     

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.     

Regular orientable embeddings of complete bipartite graphs

In this paper, it will be shown that the isomorphism classes of regular orientable embeddings of the complete bipartite graph K_n,n are in one‐to‐one correspondence with the permutations on n elements satisfying a given criterion, and the isomorphism classes of them are completely classified when n is a product of any two (not necessarily distinct) prime numbers. For other n, a lower bound of the number of those isomorphism classes of K_n,n is obtained. As a result, many new regular orientable embeddings of the complete bipartite graph are constructed giving an answer of Nedela‐?koviera's question raised in 12 . © 2005 Wiley Periodicals, Inc. J Graph Theory