¿^creative	, ars mathematica
^commons	contemporánea
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 9 (2015) 109-113
On spectral radius and energy of complete multipartite graphs
Dragan Stevanovic *
University ofPrimorska, UP IAM, Muzejski trg 2, SI-6000 Koper, Slovenia and Mathematical Institute, Serbian Academy of Science and Arts, Knez Mihajlova 36, 11000
Belgrade, Serbia
Ivan Gutman
Faculty of Science, University of Kragujevac, P.O. Box 60, 34000 Kragujevac, Serbia
Masood U. Rehman
Air University, Islamabad, Pakistan Received 18 June 2013, accepted 8 March 2014, published online 8 August 2014
Abstract
Let Kni ,n2,...,np denote the completep-partite graph, p > 1,on n = n1 + n2 + • • • + np vertices and let ni > n2 > • • • > np > 0. We show that for a fixed value of n, both the spectral radius and the energy of complete p-partite graphs are minimal for complete split graph CS(n,p — 1) and are maximal for Turan graph T(n, p).
Keywords: Spectral radius of graph, graph energy, complete multipartite graph, complete split graph, Turan graph.
Math. Subj. Class.: 05C50
1 Introduction
Let G be a simple graph on n vertices, and Ai > A2 > • • • > An be its eigenvalues (i.e., the eigenvalues of the (0,1)-adjacency matrix of G) [2, 4]. Then A1 = A1(G) is said to be the spectral radius of the graph G whereas
n
E = E(G) = Y, |Ai|	(1.1)
i=i
* Corresponding author. The work of DS was supported by Research Programme P1-0285 and Research Project J1-4021 of the Slovenian Research Agency and Research Grant ON174033 of the Ministry of Education and Science of Serbia.
E-mail addresses: dragan.stevanovic@upr.si (Dragan Stevanovic), gutman@kg.ac.rs (Ivan Gutman), (Masood U. Rehman)
©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
110
Ars Math. Contemp. 9 (2015) 115-124
is its energy. The spectral radius is one of the most thoroughly investigated graph-spectral parameters [2, 4, 3]. Also the graph energy has recently attracted much attention [6, 7]. In spite of this, not much is known on Ai and E of complete multipartite graphs [5].
Let p > 1. Denote by Kni tn2,...,np the completep-partite graph on n = n1 + n2 + • • • + np vertices. For convenience, we assume that n1 > n2 > • • • > np > 0. Two particular types of complete multipartite graphs are:
•	Complete split graph CS(n,p - 1) = Kn_p+1i1i...i1 consisting of an independent set of n - p +1 vertices and a clique of p - 1 vertices, such that each vertex of the independent set is adjacent to each vertex of the clique, and
•	Turan graph T(n,p) = K^/^...^«^^/^...^«/^ the (p + 1)-clique-free graph with maximum number of edges [10].
A fundamental result on the spectrum of complete multipartite graphs is:
Theorem 1.1 ([9, 8]). A connected graph has exactly one positive eigenvalue of its adjacency matrix if and only if it is a complete multipartite graph.
An immediate consequence of Theorem 1.1 is
Lemma 1.2. If A1 is the spectral radius of the complete multipartite graph Knii„2i...inp , then E(K«^.....^) = 2 A1.
Proof. Since all graph eigenvalues are real numbers and their sum is zero, from Eq. (1.1) follows that E(G) is equal to twice the sum of positive eigenvalues.	□
It is known that the characteristic polynomial of Knii„2i. ..inp is given by [2, 5]
^(Kni,„2,..,„p, A) = An_W 1 - ]T	J n(A + n) .	(1.2)
V ¿=1 / j=1
The spectrum of Kni i„2 . . . np consists of the spectral radius A1 determined from the equation J2p=1 A+« = 1, eigenvalue 0 with multiplicity n - p and p -1 eigenvalues situated in the intervals [-np, -np-1],..., [-n2, -n1]. In the special case n1 = n2 = • • • = np = t, the spectrum of Ktjtj...jt consists of the spectral radius t(p - 1) with unit multiplicity, eigenvalue 0 with multiplicity p(t - 1), and eigenvalue -t with multiplicity p - 1, so that
E(Kt,t,...,t) = 2(p - 1)t.
Remark 1.3. The 1-partite complete graph (when p =1 and t = n) is the edgeless graph Kn for which, consistently, A1 = E = 0. The n-partite complete graph (when p = n and t = 1) is the ordinary complete graph Kn for which, consistently, A1 = n - 1 and
E = 2(n - 1).
If p = 2, then the special case of Eq. (1.2) is
^(K„i,„2, A) = An_2(A2 - m n^ , from which the (well known) expressions for spectral radius and energy follow: A1 (Kni ,„2) = Vn1 n2,	E(Kni ,„2) = 2^n1 n2 .
Because n1 + n2 = n, for a fixed number of vertices n, we arrive at:
D. Stevanovic et al.: On spectral radius and energy of complete multipartite graphs
111
Claim 1.4. 1° A1 (Kni ,n2) and E(Kni ,n2) are minimal if n1 = n — 1 and n2 = 1. 2° A1(Kni,n2) andE(Knin2) are maximal if n1 — n2 < 1.
If p = 3, then the special case of Eq. (1.2) is
4>(KtlMM,A) = Av-z(aA3 — (ti t2 +12 is + is ti) A — 2ti t2 is) . (1.3) Using (1.3), it is relatively easy to show the following:
Claim 1.5. 1° Let n1 + n2 + ns be equal to a fixed integer n. Then the spectral radius and the energy of Kni,n2,n3 are minimal if n1 = n — 2 and n2 = ns = 1. 2° Let n1 + n2 + ns be equal to a fixed integer n. Then the spectral radius and the energy of Kni,n2,n3 are maximal if n1 — ns < 1.
The above claims were the motivation for establishing our main results:
Theorem 1.6. Let p > 2 and n1 + n2 + ■ ■ ■ + np be equal to a fixed integer n. Then the spectral radius and the energy of Kni,n2,...,np are minimal if Kni,n2,...,np = CS(n,p — 1).
Theorem 1.7. Let p > 2 and n1 + n2 + ■ ■ ■ + np be equal to a fixed integer n. Then the spectral radius and the energy of Kni,n2,..,np are maximal if Kni,n2,...,np = T(n,p).
2 Proofs of Theorems 1.6 and 1.7
Let A1 and x be, respectively, the spectral radius and the corresponding unit eigenvector of the adjacency matrix of Kni,...,np . Since A1 is a simple eigenvalue of Kni..np , similar vertices have equal x-components. Hence, we may denote by xi the common x-component of vertices in the part of Kni..np having ni vertices for i = 1,..., p. From the eigenvalue equation, we have:
p
A1 xi = £ nk xk = X — ni xi
k=i k=i
where X = Y7k=i nk xk . Then
X (2.1)
Ài + ni
Lemma 2.1. If ni — nj > 2, then
A1(Kni,...,ni — 1,...,nj + 1,...,np ) > A1(Kni ,...,ni,...,nj ,...,np ) .
Proof. Let A1, x and E denote, respectively, the spectral radius, the corresponding eigenvector, and the edge set of Kni ..,ni..,nj.,,np , and let A1, A* and E* denote, respectively, the spectral radius, the adjacency matrix, and the edge set of Kni..ni-1..,nj+1...nip . From the Variational theorem we have
Àx ^ x A. x — ^ ^ 2xu,x
u^v
*
u^v
uveE*
uveE	uv£E*\E	uv£E\E
—	Ài + 2xi(ni — 1)xi — 2xinj xj
—	Ài + 2xiX (Àn~~~ — Y^—)	(2.2)
\ Ài + ni Ài + nj 1

112
Ars Math. Contemp. 9 (2015) 115-124
by Eq. (2.1). Next, note that Knii...,nii...inj...,np has Kni,nj as an induced subgraph, so that, by the Interlacing theorem [2],
Ai > yjni nj > nj .
Therefore,
ni — 1 Uj (ni — Uj — 1)Ai — Uj ^ Ai — Uj	^
Ai + Ui Ai + Uj (Ai + Ui)(Ai + Uj) _ (Ai + Ui)(Ai + Uj)
so that Ai > Ai follows from Eq. (2.2).	□
Proof of Theorem 1.6 Let Kmi ,...,mp be the complete multipartite graph with the smallest spectral radius. If there are two parameters mi > mj > 2, then (mi +1) — (mj — 1) > 2 and from Lemma 2.1
Ai (Kmi ,...,m,i,...,m,j ,...,mp ) > Ai (Kmi ,...,m,i+i,...,m,j — i,...,mp )
contradicting the choice of Kmii...,mii...imj,...,mp . Hence, all parameters mi,..., mp are
equal to one, except for one parameter equal to n—p+1, so that Kmi,...,mp = CS(n,p—1). □
Proof of Theorem 1.7 Let Km 1 ,...,mp be the complete multipartite graph with the largest spectral radius. It is apparent from Lemma 2.1, that |mi — mj | < 1 holds for all i = j, as otherwise, assuming mi — mj > 2,
Ai (Kmi ,...,m,i — i,...,m,j + i,...,mp ) > Ai (Kmi ,...,mi,...,mj ,...,mp )
contradicting the choice of Kmii...,mii...imj,...,mp . The condition |mi — mj | < 1 for i = j implies that each parameter mi is equal to either |_n/pj or [n/p], so that Kmi,...,mp = T (n,p).	□
Remark 2.2. Delorme [5] proved (a bit too concisely) that changing the arbitrary e parameters of a complete multipartite graph by their average value increases the spectral radius by relying on the characteristic polynomial. While this result can be substituted for Lemma 2.1 in the proofs of Theorems 1.6 and 1.7, Lemma 2.1 is an independent result based on the principal eigenvector and inspired by the rotation lemma from [1].
Remark 2.3. Delorme also asked in [5] whether the spectral radius of complete multipartite graph Kni,...,np is a concave function on the (p — 1)-dimensional simplex Y :
ni = n A (Vi € {1,... ,p})(ni > 0), i.e., whether
Ai(Ki(ni,...,np) + (i-i)(mi,...,mp)) > t Ai (Kni ,...,np ) + (1 — t) Ai(Kmi,..,mp )
for any two points (ni,..., np), (mi,..., mp) € Y and each t € [0,1] such that
t(ni,. .., np) + (1 — t)(mi, ..., mp) € Y?
Delorme proved this affirmatively for p < 3 in [5]. We tested it computationally for t = 0.5, p € {4,..., 10} and n < 33 and found no counterexamples to the above question on these simplices.
D. Stevanovic et al.: On spectral radius and energy of complete multipartite graphs
113
References
[1]	F. Belardo, E. M. Li Marzi, S. K. Simic, Some results on the index of unicyclic graphs, Linear Algebra Appl. 416 (2006), 1048-1059.
[2]	D. CvetkoviC, M. Doob, H. Sachs, Spectra of Graphs—Theory and Application, Academic Press, New York, 1980.
[3]	D. Cvetkovic, P. Rowlinson, The largest eigenvalue of a graph: A survey, Lin. Multilin. Algebra 28 (1990), 3-33.
[4]	D. Cvetkovic, P. Rowlinson, S. Simic, An Introduction to the Theory of Graph Spectra, Cambridge Univ. Press, Cambridge, 2010.
[5]	C. Delorme, Eigenvalues of complete multipartite graphs, Discrete Math. 312 (2012), 25322535.
[6]	I. Gutman, The energy of a graph: Old and new results, in: A. Betten, A. Kohnert, R. Laue, A. Wassermann (eds.), Algebraic Combinatorics and Applications, Springer, Berlin, 2001, 196211.
[7]	X. Li, Y. Shi, I. Gutman, Graph Energy, Springer, New York, 2012.
[8]	M. M. Petrovic, The spectrum of infinite complete multipartite graphs, Publ. Inst. Math. (Belgrade) (N.S.) 31(45) (1982), 169-176.
[9]	J. H. Smith, Some properties of the spectrum of a graph, in: R. Guy, H. Hanani, N. Sauer, J. Schonheim (eds.), Combinatorial Structures and Their Applications, Gordon & Breach, New York, 1970, 403-406.
[10] P. Turan, On an extremal problem in graph theory, Mat. Fiz. Lap. 48 (1941), 436-452.