Signless Laplacian Characteristic Polynomials of Complete Multipartite Graphs

For a simple graph G,let matrix Q(G)=D(G) + A(G) be it's signless Laplacian matrix and Q G (λ)=det(λI Q) it's signless Laplacian characteristic polynomial,where D(G) denotes the diagonal matrix of vertex degrees of G,A(G) denotes its adjacency matrix of G.If all eigenvalues of Q G (λ) are integral,then the graph G is called Q-integral.In this paper,we obtain that the signless Laplacian characteristic polynomials of the complete multi-partite graphs G=K(n_1,n_2,···,n_t).We prove that the complete t-partite graphs K(n,n,···,n)t are Q-integral and give a necessary and sufficient condition for the complete multipartite graphs K(m,···,m)s(n,···,n)t to be Q-integral.We also obtain that the signless Laplacian characteristic polynomials of the complete multipartite graphs K(m,···,m,)s1(n,···,n,)s2(l,···,l)s3.

Distance Integral Complete Multipartite Graphs with s=5, 6

Let D(G) =(d_(ij))_(n×n) denote the distance matrix of a connected graph G with order n, where d_(ij) is equal to the distance between vertices viand vjin G. A graph is called distance integral if all eigenvalues of its distance matrix are integers. In 2014, Yang and Wang gave a sufficient and necessary condition for complete r-partite graphs K_(p1,p2,···,pr)=K_(a1·p1,a2·p2,···,as···ps) to be distance integral and obtained such distance integral graphs with s = 1, 2, 3, 4. However distance integral complete multipartite graphs K_(a1·p1,a2·p2,···,as·ps) with s > 4 have not been found. In this paper, we find and construct some infinite classes of these distance integral graphs K_(a1·p1,a2·p2,···,as·ps) with s = 5, 6. The problem of the existence of such distance integral graphs K_(a1·p1,a2·p2,···,as·ps) with arbitrarily large number s remains open.

The Interval Graph Completion Problem for the Complete Multipartite Graphs

The interval graph completion problem of a graph G includes two class problems： the profile problem and the pathwidth problem, denoted as P（G） and PW（G） respectively, where the profile problem is to find an interval supergraph with the smallest possible number of edges; the pathwidth problem is to find an interval supergraph with the smallest possible cliquesize. These two class problems have important applications to numerical algebra, VLSI- layout and algorithm graph theory respectively; And they are known to be NP-complete for general graphs. Some classes of special graphs have been investigated in the literatures. In this paper the exact solutions of the profile and the pathwidth of the complete multipartite graph Kn1,n2,...nr （r≥ 2） are determined.

Chromatic Choosability of a Class of Complete Multipartite Graphs

A graph G is called to be chromatic choosable if its choice number is equal to its chromatic number. In 2002, Ohba conjectured that every graph G with 2Х（G） ＋ 1 or fewer vertices is chromatic choosable. It is easy to see that Ohba＇s conjecture is true if and only if it is true for complete multipartite graphs. But at present only for some special cases of complete multipartite graphs, Ohba＇s conjecture have been verified. In this paper we show that graphs K6,3,2＊（k-6）,1＊4 （k ≥ 6） is chromatic choosable and hence Ohba＇s conjecture is true for the graphs K6,3,2＊（k-6）,1＊4 and all complete k-partite subgraphs of them.

On the Seidel Integral Complete Multipartite Graphs

For a simple undirected graph G, denote by λ（G） the （0, 1）-adjacency matrix of G. Let the matrix S（G） = J-I-2A（G） be its Seidel matrix, and let SG（A） = det（AI-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 SG（λ） are integral, then the graph G is called S-integral, In this paper, our main goal is to investigate the eigenvalues of SG（A） for the complete multipartite graphs G = Kn1,n2,...,n,. A necessary and sufficient condition for the complete tripartite graphs Km,n,t and the complete multipartite graphs Km,.... m,n,...,n to be S-integral is given, respectively.

Bondage and Reinforcement Number of γ_f for Complete Multipartite Graph

The bondage number of γ f, b f(G) , is defined to be the minimum cardinality of a set of edges whose removal from G results in a graph G′ satisfying γ f(G′)> γ f(G) . The reinforcement number of γ f, r f(G) , is defined to be the minimum cardinality of a set of edges which when added to G results in a graph G′ satisfying γ f(G′)< γ f(G) . G.S.Domke and R.C.Laskar initiated the study of them and gave exact values of b f(G) and r f(G) for some classes of graphs. Exact values of b f(G) and r f(G) for complete multipartite graphs are given and some results are extended.

Triple Crossing Numbers of Graphs

We introduce the triple crossing number, a variation of the crossing number, of a graph, which is the minimal number of crossing points in all drawings of the graph with only triple crossings. It is defined to be zero for planar graphs, and to be infinite for non-planar graphs which do not admit a drawing with only triple crossings. In this paper, we determine the triple crossing numbers for all complete multipartite graphs which include all complete graphs.

Maximizing the Minimum and Maximum Forcing Numbers of Perfect Matchings of Graphs

Let G be a simple graph with 2n vertices and a perfect matching.The forcing number f(G,M) of a perfect matching M of G is the smallest cardinality of a subset of M that is contained in no other perfect matching of G.Among all perfect matchings M of G,the minimum and maximum values of f(G,M) are called the minimum and maximum forcing numbers of G,denoted by f(G) and F(G),respectively.Then f(G)≤F(G) ≤n-1.Che and Chen(2011) proposed an open problem:how to characterize the graphs G with f(G)=n-1.Later they showed that for a bipartite graph G,f(G)=n-1 if and only if G is complete bipartite graph K_(n,n).In this paper,we completely solve the problem of Che and Chen,and show that f(G)=n-1 if and only if G is a complete multipartite graph or a graph obtained from complete bipartite graph K_(n,n) by adding arbitrary edges in one partite set.For all graphs G with F(G)=n-1,we prove that the forcing spectrum of each such graph G forms an integer interval by matching 2-switches and the minimum forcing numbers of all such graphs G form an integer interval from [n/2] to n-1.

THE LINEAR ARBORICITY OF COMPOSITION GRAPHS

The linear arboricity la(G) of a graph G is the minimum number of linear forests which partition the edges of G. Akiyama, Exoo and Harary conjectured that la(G) = [△(G)+1/2] for any regular graph G. In this paper, we prove the conjecture for some composition graphs, in particular, for complete multipartite graphs.