| Title:
|
On graphs with the largest Laplacian index (English) |
| Author:
|
Liu, BoLian |
| Author:
|
Chen, Zhibo |
| Author:
|
Liu, Muhuo |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
58 |
| Issue:
|
4 |
| Year:
|
2008 |
| Pages:
|
949-960 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
Let $G$ be a connected simple graph on $n$ vertices. The Laplacian index of $G$, namely, the greatest Laplacian eigenvalue of $G$, is well known to be bounded above by $n$. In this paper, we give structural characterizations for graphs $G$ with the largest Laplacian index $n$. Regular graphs, Hamiltonian graphs and planar graphs with the largest Laplacian index are investigated. We present a necessary and sufficient condition on $n$ and $k$ for the existence of a $k$-regular graph $G$ of order $n$ with the largest Laplacian index $n$. We prove that for a graph $G$ of order $n \geq 3$ with the largest Laplacian index $n$, $G$ is Hamiltonian if $G$ is regular or its maximum vertex degree is $\triangle (G)=n/2$. Moreover, we obtain some useful inequalities concerning the Laplacian index and the algebraic connectivity which produce miscellaneous related results. (English) |
| Keyword:
|
eigenvalue |
| Keyword:
|
Laplacian index |
| Keyword:
|
algebraic connectivity |
| Keyword:
|
semi-regular graph |
| Keyword:
|
regular graph |
| Keyword:
|
Hamiltonian graph |
| Keyword:
|
planar graph |
| MSC:
|
05C50 |
| MSC:
|
15A36 |
| MSC:
|
15A42 |
| idZBL:
|
Zbl 1174.05078 |
| idMR:
|
MR2471159 |
| . |
| Date available:
|
2010-07-21T08:06:34Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/140433 |
| . |
| Reference:
|
[1] Bonday, J. A., Murty, U. S. R.: Graph Theory with Applications.Macmillan London (1976). |
| Reference:
|
[2] Cvetkovic, D. M., Doob, M., Sachs, H.: Spectra of Graphs. Theory and Applications.VEB Deutscher Verlag der Wissenschaften Berlin (1980). |
| Reference:
|
[3] Fiedler, M.: Algebraic connectivity of graphs.Czechoslovak Math. J. 23 (1973), 298-305. Zbl 0265.05119, MR 0318007 |
| Reference:
|
[4] Gracssi, R.: Relevant inequalities in graph connectivity.Arch. Ineqal. Appl. 2 (2004), 183-198. MR 2106953 |
| Reference:
|
[5] Gutman, I.: The star is the tree with greatest Laplacian eignvalue.Kragujevac J. Math. 24 (2002), 61-65. MR 1947659 |
| Reference:
|
[6] Haemers, W. H.: Interlacing eigenvalues and graphs.Linear Algebra Appl. 227-228 (1995), 593-616. Zbl 0831.05044, MR 1344588 |
| Reference:
|
[7] Harary, F.: Graph Theory.Addison-Wesley Reading (1969). Zbl 0196.27202, MR 0256911 |
| Reference:
|
[8] Merris, R.: Laplacian matrices of graphs: A survey.Linear Algebra Appl. 197-198 (1994), 143-176. Zbl 0802.05053, MR 1275613 |
| . |
