tailieunhanh - Minimizing graph of the connected graphs whose complements are bicyclic with two cycles

A connected graph containing two or three cycles is called a bicyclic graph if its number of edges is equal to its number of vertices plus one. In this paper, we characterize the minimizing graph among all the connected graphs that belong to a class of graphs whose complements are bicyclic with two cycles. | Turk J Math (2017) 41: 1433 – 1445 ¨ ITAK ˙ c TUB ⃝ Turkish Journal of Mathematics doi: Research Article Minimizing graph of the connected graphs whose complements are bicyclic with two cycles Muhammad JAVAID∗ Department of Mathematics, School of Science, University of Management and Technology (UMT), Lahore, Pakistan Received: • Accepted/Published Online: • Final Version: Abstract: In a certain class of graphs, a graph is called minimizing if the least eigenvalue of its adjacency matrix attains the minimum. A connected graph containing two or three cycles is called a bicyclic graph if its number of edges is equal to its number of vertices plus one. In this paper, we characterize the minimizing graph among all the connected graphs that belong to a class of graphs whose complements are bicyclic with two cycles. Key words: Adjacency matrix, least eigenvalue, bicyclic graphs 1. Introduction Let G be a finite, simple, and undirected graph with the vertex-set V (G) = {vi : 1 ≤ i ≤ n} and the edgeset E(G) such that |V (G)| = n and |E(G)| = m are the order and size of the graph G , respectively. The adjacency matrix A(G) = [ai,j ] of the graph G is a matrix of order n, where ai,j = 1 if vi is adjacent to vj and ai,j = 0 otherwise. The zeros of det(A(G) − λI) are called the eigenvalues of A(G) , where I is an identity matrix of order n . Since A(G) is real and symmetric, all the eigenvalues say λ1 (G) , λ2 (G) ,., λn (G) are real and called the eigenvalues of the graph G . If λ1 (G) is the least, then one can arrange the eigenvalues as λ1 (G) ≤ λ2 (G) ≤ . ≤ λn (G) and the eigenvector corresponding to the least eigenvalue is called the first eigenvector. For further study, we refer to [3, 4]. In a certain class of graphs, a graph is called minimizing if the least eigenvalue of its adjacency matrix attains the minimum. Let G(m, n) denote the class of connected graphs of .