
تعداد نشریات | 43 |
تعداد شمارهها | 1,688 |
تعداد مقالات | 13,864 |
تعداد مشاهده مقاله | 32,921,942 |
تعداد دریافت فایل اصل مقاله | 13,029,971 |
Chromatic number and signless Laplacian spectral radius of graphs | ||
Transactions on Combinatorics | ||
مقاله 6، دوره 11، شماره 4، اسفند 2022، صفحه 327-334 اصل مقاله (444.37 K) | ||
نوع مقاله: Research Paper | ||
شناسه دیجیتال (DOI): 10.22108/toc.2021.129720.1876 | ||
نویسنده | ||
Mohammad Reza Oboudi* | ||
Department of Mathematics, College of Sciences, Shiraz University, Shiraz, 71457-44776, Iran | ||
چکیده | ||
For any simple graph $G$, the signless Laplacian matrix of $G$ is defined as $D(G)+A(G)$, where $D(G)$ and $A(G)$ are the diagonal matrix of vertex degrees and the adjacency matrix of $G$, respectively. %Let $\chi(G)$ be the chromatic number of $G$ Let $q(G)$ be the signless Laplacian spectral radius of $G$ (the largest eigenvalue of the signless Laplacian matrix of $G$). In this paper we find some relations between the chromatic number and the signless Laplacian spectral radius of graphs. In particular, we characterize all graphs $G$ of order $n$ with odd chromatic number $\chi$ such that $q(G)=2n\Big(1-\frac{1}{\chi}\Big)$. Finally we show that if $G$ is a graph of order $n$ and with chromatic number $\chi$, then under certain conditions, $q(G)<2n\Big(1-\frac{1}{\chi}\Big)-\frac{2}{n}$. This result improves some previous similar results. | ||
کلیدواژهها | ||
Chromatic number؛ Majorization؛ Signless Laplacian matrix؛ Signless Laplacian spectral radius | ||
مراجع | ||
[1] D. M. Cvetković, M. Doob and H. Sachs, Spectra of Graphs, Theory and Application, Academic Press, Inc., New York, 1980. [2] D. Cvetković, P. Rowlinson and S. Simić, An introduction to the theory of graph spectra, London Mathematical Society Student Texts, 75, Cambridge University Press, Cambridge, 2010. [3] D. Cvetković, P. Rowlinson and S. Simić, Eigenvalue bounds for the signless laplacian,Publ. Inst. Math., (Beograd) 81 (2007) 11–27. [4] C .S. Edwards, C. H. Elphick, Lower bounds for the clique and the chromatic numbers of a graph, Discrete Appl. Math., 5 (1983) 51–64. [5] A. W. Marshall, I. Olkin and B. C. Arnold, Inequalities: Theory of Majorization and Its Applications, Second Edition, Springer, New York, 2011. [6] V. Nikiforov, Chromatic number and spectral radius, Linear Algebra Appl., 426 (2007) 810–814.
[7] M. R. Oboudi, A relation between the signless Laplacian spectral radius of complete multipartite graphs and majorization, Linear Algebra Appl., 565 (2019) 225–238. [8] M. R. Oboudi, Distance spectral radius of complete multipartite graphs and majorization, Linear Algebra Appl., 583 (2019) 134–145. [9] M. R. Oboudi, Majorization and the spectral radius of starlike trees, J. Comb. Optim., 36 (2018) 121–129.
[10] M. R. Oboudi, On the difference between the spectral radius and maximum degree of graphs, Algebra Discrete Math., 24 (2017) 302–307. [11] M. R. Oboudi, On the largest real root of independence polynomials of graphs, an ordering on graphs, and starlike trees, arXiv:1303.3222. [12] M. R. Oboudi, On the third largest eigenvalue of graphs, Linear Algebra Appl., 503 (2016) 164–179.
[13] H. S. Wilf, Spectral bounds for the clique and independence numbers of graphs, J. Combin. Theory Ser. B, 40 (1986) 113–117. [14] H. S. Wilf, The eigenvalues of a graph and its chromatic number, J. London Math. Soc., 42 (1967) 330–332.
[15] G. Yu, Y. Wu and J. Shu, Signless Laplacian spectral radii of graphs with given chromatic number, Linear Algebra Appl., 435 (2011) 1813–1822. | ||
آمار تعداد مشاهده مقاله: 783 تعداد دریافت فایل اصل مقاله: 655 |