Journal of Applied Mathematics and Physics
Vol.06 No.10(2018), Article ID:88093,7 pages
10.4236/jamp.2018.610181
The Signless Laplacian Spectral Radius of Some Special Bipartite Graphs
Yun Yang
School of Science, University of Shanghai for Science and Technology, Shanghai, China
Copyright © 2018 by author and Scientific Research Publishing Inc.
This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).
http://creativecommons.org/licenses/by/4.0/
Received: September 28, 2018; Accepted: October 26, 2018; Published: October 29, 2018
ABSTRACT
This paper mainly researches on the signless laplacian spectral radius of bipartite graphs . We consider how the signless laplacian spectral radius of changes under some special cases. As application, we give two upper bounds on the signless laplacian spectral radius of , and determine the graphs that obtain the upper bounds.
Keywords:
The Signless Laplacian Spectral Radius, The Largest Eigenvalue, Bipartite Graph
1. Introduction
Let be a connected graph of order with vertex set and edge set is considered in this paper. In spectral graph theory, one usually uses the spectrum of related matrices to characterize the structure of graphs. The most studied matrix associated with G appears to be the adjacency matrices with when there’s an edge between and , otherwise . Some other well studied matrices are the Laplacian matrix and the signless Laplacian matrix of G. The former is defined by where is the degree diagonal matrix, whereas the latter is defined as . For polynomials of with only real roots, let be the largest root of ; the maximum eigenvalue of the (unsigned) Laplace of graph G is denoted as , and respectively represent the minimum and maximum degrees of the graph.
The actical [1] studied the bipartite graph with the fixed order of n and the size of m, and the graph with the largest Laplace spectrum radius in the graph class was determined, as well as the upper bound of the Laplace spectrum radius of . The actical [2] studies the bipartite graph of the fixed order of n and the size of , and describes the structure of the bipartite graph with maximum adjacency spectrum radius. Reference [3] is to determine the structure of the bipartite graph of the fixed order of n and the size of m after removing the given k edges. In Reference [4] , by studying the signless Laplacian spectrum, the structure of the maximum spectrum of bipartite graphs with fixed order and size is determined, and the upper and lower bounds of the spectrum are given again.
Inspired by the above results, this paper studies the bipartite graph . We fix the order and the size of the bipartite graphs G, and observe what influence may have on the signless Laplacian radius of G after transforming the neighborhood of some vertexes.
Before giving the main conclusion of this paper, we first introduce the bipartite graph , and then give the definitions of equitable division and quotient matrix that need to be used in the later proof:
Definition 1.1. Let G be a connected bipartite graph with two vertex sets of U and V, each vertex set has the following partition, , and every vertex in is connected to all vertexes in and , every vertex in is connected to all vertexes in , every vertex in is connected to all vertexes in and , each vertex in is connected to all vertexes in , showing in Figure 1. If the number of vertexes in is respectively, and the induction sub-graphs of are all r-regular,then denoting . For convenience, the order and the size of G are n and m, that is
(1)
Figure 1. .
Definition 1.2. Let G be a connected graph, the vertex set of G is divided into . If every vertex in has the same number of adjacent vertex in , for any , such partitions are called equitable division of G.
Definition 1.3. Let A as real symmetric matrix, and its row and column are divided equally. The matrix formed by elements that is the average row sum of each sub-blocks, according to the position of its sub-blocks is called the quotient matrix of A.
Lemma 1. [5] The spectral radius of G must be the eigenvalue of any quotient matrix of G.
Lemma 2. [5] For any graph G, let be the maximum (signless) Laplace eigenvalue of G, then .
Lemma 3. Let be a connected bipartite graph and defined in definition 1.1, then is an equitable division.
Proof: Because every vertex in is connected to all vertexes in and , so every vertex of has the same number of adjacent vertexes in . Similarly, every vertex in has the same number of adjacent vertexes in , every vertex of has the same number of adjacent vertexes in , every vertex of has the same number of adjacent vertexes with . So is an equitable divide.
2. Regular
In this section, we mainly discuss the graph , that is, the induction sub-graphs of are all independent sets and are all 0-regular graphs. For such figure , we observe the change of the maximum eigenvalue of the graph by taking neighborhood transformation, and then determine the structure of the graph when the graph achieve the maximum spectral radius.
Lemma 2.1. Let , when , .
If , , else
Proof: Since is an equitable division of G, and are a quotient matrix of Q(G) and Q(H),
(2)
(3)
The characteristic polynomials of and are obtained by calculation as follows:
(4)
(5)
(6)
The largest root of is denoted as . By Lemma 3, it’s easily to know , , so , then
When ,
so , then .
When ,
so .
When ,
so .
3. Complete Graph
The induction sub-graphs of studied in the second section are all independent sets, namely 0-regular graphs. Based on the second section, this section continues to study the situation that are all complete graphs. For convenience, this paper write this graphas .
Lemma 3.1. Let , will be constant when and .
Proof: Since is an equitable division of G, and are a quotient matrix of Q(G) and Q(H)
(7)
(8)
The characteristic polynomials of and are obtained by calculation as follows:
(9)
(10)
(11)
First of all need to prove , because
Set
(12)
There is a common factor constant a in , and a does not affect the root of . Therefore, for the convenience of discussion, we study the polynomial , after elimination of a is equal to the root of , because can be viewed as a unary quadratic equation about a, what’s more , so is constant. Let
(13)
the root of are
, and
Because , So the range of the largest root of is . Moreover , so we assume the largest root of is .
Next proof . We know
and
by calculation the root of is , so is monotonically decreasing in
and since when , so , then proofed.
Finally proof , , by calculation
and
when , so , .
Because , and is the largest root of the characteristic polynomial . There have
so .
Lemma 3.2. Let , , then is constant.
Proof: Since is an equitable division of G, and are a quotient matrix of Q(G) and Q(H)
(14)
(15)
The characteristic polynomials , of and are obtained by calculation as follows:
(16)
(17)
let
,
(18)
because , we obtain that is an open up quadratic function, and , because of , we let , and get the derivative for a and n, ,
, so . Let the two roots be and respectively, and . By the root formula , , both can be calculated. is monotonically increasing with respect to a, so . When , then
the four roots of are , , and . When , then . when , then , have two intersections, and haven’t gotten to the maximum yet, so is constant.
4. Conclusion
It can be seen from the above conclusions, the structure of the graph is when the signless laplacian spectral radius of G has reached maximum. Similarly, the structure of the graph is , when the signless laplacian spectral radius of G has reached maximum, and the structure of the graph is , when the signless laplacian spectral radius of G has reached maximum.
Conflicts of Interest
The author declares no conflicts of interest regarding the publication of this paper.
Cite this paper
Yang, Y. (2018) The Signless Laplacian Spectral Radius of Some Special Bipartite Graphs. Journal of Applied Mathematics and Physics, 6, 2159-2165. https://doi.org/10.4236/jamp.2018.610181
References
- 1. Zhang, H. and Li, S. (2017) On the Laplacian Spectral Radius of Bipartite Graphs with Fixed Order and Size. Discrete Applied Mathematics, 229, 139-147. https://doi.org/10.1016/j.dam.2017.05.011
- 2. Petrovic, M. and Simic, S. (2015) A Note on Connected Bipartite of Fixed Order and Size with Maximal Index. Linear Algebra and Its Applications, 483, 21-29. https://doi.org/10.1016/j.laa.2015.05.013
- 3. Zhang, X.L. and Zhang, H.F. (2008) The Laplacian Spectra Radius of Some Bipartite Graphs. Linear Algebra and Its Applications, 428, 1610-1619. https://doi.org/10.1016/j.laa.2007.10.007
- 4. Cvetkovic, D., Rowlinson, P. and Simic, S.K. (2007) Eigenvalue Bounds for the signlesslapacian. Publications de l’Institut Mathematique, 81, 11-27. https://doi.org/10.2298/PIM0795011C
- 5. Cvetkovic, D., Rowlinson, P. and Simic, S. (2010) An Introduction to the Theory of Graph Spectra. Cambridge University Press, Cambridge.