On the index of tricyclic graphs with perfect matchings. (English) Zbl 1175.05082
Summary: Let \(\mathcal T(2k)\) be the set of all tricyclic graphs on \(2k\) (\(k\geqslant 2\)) vertices with perfect matchings. In this paper, we discuss some properties of the connected graphs with perfect matchings, and then determine graphs with the largest index in \(\mathcal T(2k)\).
MSC:
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
| 05C35 | Extremal problems in graph theory |
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
References:
| [1] | Bell, F. K., On the maxmal index of connected graphs, Linear Algebra Appl., 144, 135-151 (1993) · Zbl 0764.05057 |
| [2] | Brualdi, R. A.; Solheid, E. S., On the index of connected graphs, Publ. Inst. Math. (Beograd), 39, 53, 45-54 (1986) · Zbl 0603.05028 |
| [3] | Chang, A.; Tian, F., On the index of unicyclic graphs with perfect matching, Linear Algebra Appl., 370, 237-250 (2003) · Zbl 1030.05074 |
| [4] | Chang, A.; Tian, F.; Yu, A. M., On the index of bicyclic graphs with perfect matchings, Disc. Math., 283, 51-59 (2004) · Zbl 1064.05118 |
| [5] | Collatz, L.; Sinogowitz, U., Spektren endlicher grapen, Abh. Math. Sem. Univ. Hamburg, 21, 63-77 (1957) · Zbl 0077.36704 |
| [6] | Hoffman, A. J.; Smith, J. H., On the spectral radii of topologically equivalent graphs, (Fiedler, Recent Advances in Graph Theory (1975), Academia Praha: Academia Praha New York), 273-281 · Zbl 0327.05125 |
| [7] | Hou, Y. P.; Li, J. S., Bounds on the largest eigenvalues of trees with a given size of matching, Linear Algebra Appl., 342, 203-217 (2002) · Zbl 0992.05055 |
| [8] | Cvetković, D.; Doob, M.; Sachs, H., Spectra of Graphs (1980), Academic Press: Academic Press New York, second revised ed., Barth, Heidelberg, 1995 · Zbl 0458.05042 |
| [9] | Cvetković, D.; Rowlinson, P., On the connected graphs with maximal index, Publ. Inst. Math. (Beograd), 44, 58, 29-34 (1986) · Zbl 0661.05041 |
| [10] | Cvetković, D.; Rowlinson, P., The largest eigenvalues of a graph: a survey, Linear Multilinear Algebra, 28, 3-33 (1990) · Zbl 0744.05031 |
| [11] | Geng, X. Y.; Li, S. C., The spectral radius of tricyclic graph with \(n\) vertices and \(k\) pendent vertices, Linear Algebra Appl., 428, 2639-2653 (2008) · Zbl 1218.05092 |
| [12] | Guo, J. M.; Shao, J. Y., On the spectral radius of trees with fixed diameter, Linear Algebra Appl., 413, 1, 131-147 (2006) · Zbl 1082.05060 |
| [13] | Guo, S. G., On the spectral radius of bicyclic graphs with \(n\) vertices and diameter \(d\), Linear Algebra Appl., 422, 119-132 (2007) · Zbl 1112.05064 |
| [14] | Guo, S. G.; Xu, G. H.; Chen, Y. G., On the spectral radius of trees with \(n\) vertices and diameter \(d\), Adv. Math. (China), 34, 6, 683-692 (2005), (in Chinese) · Zbl 1482.05192 |
| [15] | Hong, Y., On the spectra of unicyclic graphs, J. East China Normal Unir. (Nat. Sci. Ed.), 1, 1, 31-34 (1986), (in Chinese) · Zbl 0603.05030 |
| [16] | Li, Q.; Feng, K. Q., On the largest eigenvalue of graphs, Acta Math. Appl. Sinica, 2, 167-175 (1979), (in Chinese) |
| [17] | Li, S. C.; Li, X. C.; Zhu, Z. X., On tricyclic graphs with minimal energy, Match Commun. Math. Comput. Chem., 59, 397-419 (2008) · Zbl 1164.05041 |
| [18] | Liu, H.; Lu, M.; Tian, F., On the spectral radius of graphs with cut edges, Linear Algebra Appl., 389, 139-145 (2004) · Zbl 1053.05080 |
| [19] | Schwenk, A., Computing the characteristic polynomial of a graph, (Bary, R.; Harary, F., Graphs and Combinatorics. Graphs and Combinatorics, Lecture Notes in Mathematics, vol. 406 (1974), Springer-Verlag: Springer-Verlag Berlin), 153-172 · Zbl 0308.05121 |
| [20] | Simić, S. K., On the largest eigenvalue of unicyclic graphs, Publ. Inst. Math. (Beograd), 42, 56, 1319 (1987) · Zbl 0641.05040 |
| [21] | Simić, S. K., On the largest eigenvalue of bicyclic graphs, Publ. Inst. Math. (Beograd) (NS), 46, 60, 101-106 (1989) · Zbl 0747.05058 |
| [22] | Wu, B.; Xiao, E.; Hong, Y., The spectral radius of trees on \(k\) pendent vertices, Linear Algebra Appl., 395, 343-349 (2005) · Zbl 1057.05057 |
| [23] | Xu, G. H., On the Spectral Radius of Trees with Perfect Matchings. On the Spectral Radius of Trees with Perfect Matchings, Combinatorics and Graph Theory (1997), World Scientific: World Scientific Singapore |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
