On The Spectral Radius And Q-spectral Radius Of Triangle-free K-cyclic Graphs

Graph theory is a branch of mathematics that widely used and a powerful tool to handle Discrete mathematics. There are various matrices that are naturally associated with a graph, such as the adjacency matrix, the Laplacian matrix,the quasi(signless) Laplacian matrix, the distance matrix, and so on. One of the main problems of algebraic graph theory is to determine precisely whether,or how, properties of graphs are re?ected in the algebraic properties(especially eigenvalues) of such matrices.Among the above mentioned matrices of graphs, the most important three are the adjacency matrix, the Laplacian matrix and the quasi Laplacian matrix of graphs. The eigenvalues of them are the invariants of graphs under isomorphism.The largest eigenvalues of them are called the spectral radius, spectral radius of Laplacian and quasi Laplacian spectral radius of graphs.For a given set of graphs, ?nd the upper bound on the spectral radius of graphs in the set and characterize the graphs in which the maximal spectral radius is attained, which is a problem about the spectral radius of graphs raised by Brualdi and Solheid in 1986. Since then, this problem is extensively studied.It is called ”The Brualdi-Solheid Problem”, And be transplanted to the Laplacian spectral radius and quasi Laplacian spectral radius which still hot so far. Recently,Nikiforov et al., combining spectral graph theory with the extremal graph theory,proposed the spectral Tur′an problem :“Given a graph F, what is the maximum spectral radius of a graph G of order n, with no subgraph isomorphic to F ?”In 2013, Nikiforov et al. proposed the corresponding quasi Laplacian spectral type Tur′an problem:“Given a graph F, what is the maximum quasi Laplacian spectral radius of a graph G of order n, with no subgraph isomorphic to F ?”It is not di?erent to see, after the two class problems are special cases of the Brualdi-Solheid problem.K-cyclic graphs are connected graphs in which the number of edges equals the number of vertices plus k- 1, which is especially called unicyclic graph, bicyclic graph and tricyclic graph, respectively when k = 1, k = 2 and k = 3. A graph is a cactus if any two of its cycles have at most one common vertex. In this paper,we determine the maximal quasi Laplacian spectral radius together with the corresponding extremal graph among all triangle-free k-cyclic graphs of order n.Moreover, we give the ?rst ?ve triangle-free unicyclic graphs on n(n ≥ 8) vertices,the ?rst eight triangle-free bicyclic graphs on n(n ≥ 12) vertices, the ?rst nine triangle-free tricyclic graphs on n(n ≥ 16) vertices, and the ?rst ?ve triangle-free cactus graphs with n vertices and k cycles, where n ≥ 3k + 5, according to the signless Laplacian spectral radius. Besides, we determine the ?rst and the second spectral radius with the corresponding extremal graph among all triangle-free bicyclic graphs of order n.