Search

An edge labeling of a connected graph G = (V , E) is said to be local antimagic if it is a bijection f : E → { 1 , ... , | E | } such that for any pair of adjacent vertices x and y, f + (x) ≠ f + (y) , where the induced vertex label f + (x) = ∑ f (e) , with e ranging over all the edges incident to x. The local antimagic chromatic number of G, denoted by χ la (G) , is the minimum number of distinct induced vertex labels over all local antimagic labelings of G. In this paper, we show the existence of infinitely many bipartite and tripartite graphs with χ l a = 2 , 3. [ABSTRACT FROM AUTHOR]

Let G be a graph with adjacency matrix A (G) and D (G) be the diagonal matrix of the degrees of G. Nikiforov (2017) defined the matrix A α (G) as A α (G) = α D (G) + (1 − α) A (G) , α ∈ [ 0 , 1 ]. The A α -spectral radius is the largest eigenvalue of A α (G). Let G m d be the set of all connected graphs with size m and diameter d. In this paper, we determine the graphs with maximal A α -spectral radius among all graphs in G m d. [ABSTRACT FROM AUTHOR]

For a simple graph G , let n (G) , η (G) , r (G) and g (G) be respectively the order, the nullity, the rank and the girth of G. It was shown by Cheng and Liu (2007) that for every graph G , η (G) ≤ { n (G) − g (G) + 2 if 4 | g (G) n (G) − g (G) if 4 ∤ g (G) . Connected graphs G with η (G) = n (G) − g (G) + 2 and n (G) − g (G) respectively have been characterized by Zhou et al. (2021). In this paper, we characterize connected graphs G with η (G) = n (G) − g (G) − 1. [ABSTRACT FROM AUTHOR]

Abstract: The normalized algebraic connectivity of a graph G, denoted by , is the second smallest eigenvalue of its normalized Laplacian matrix. In this paper, we firstly determine all trees with . Then we classify such trees into six classes and prove that for , where and . At the same time, the values of the normalized algebraic connectivity for the six classes of trees are provided, respectively. These results are similar to those on the algebraic connectivity which were obtained by Yuan et al. (2008) [8]. [Copyright &y& Elsevier]

Abstract: The second largest Laplacian eigenvalue of a graph is the second largest eigenvalue of the associated Laplacian matrix. In this paper, we study extremal graphs for the extremal values of the second largest Laplacian eigenvalue and the Laplacian separator of a connected graph, respectively. All simple connected graphs with second largest Laplacian eigenvalue at most 3 are characterized. It is also shown that graphs with second largest Laplacian eigenvalue at most 3 are determined by their Laplacian spectrum. Moreover, the graphs with maximum and the second maximum Laplacian separators among all connected graphs are determined. [Copyright &y& Elsevier]

Abstract: The Laplacian spectral radius of a graph G is the largest eigenvalue of its Laplacian matrix. In this paper, the first three smallest values of the Laplacian spectral radii among all connected graphs with clique number are obtained. [Copyright &y& Elsevier]

Abstract: The Hosoya index and the Merrifield–Simmons index of a graph are defined as the total number of the matchings (including the empty edge set) and the total number of the independent vertex sets (including the empty vertex set) of the graph, respectively. Let be the set of connected -vertex graphs with connectivity at most . In this note, we characterize the extremal (maximal and minimal) graphs from with respect to the Hosoya index and the Merrifield–Simmons index, respectively. [Copyright &y& Elsevier]

Abstract: The algebraic connectivity of is the second smallest eigenvalue of its Laplacian matrix. Let be the set of all unicyclic graphs of order . In this paper, we will provide the ordering of unicyclic graphs in up to the last seven graphs according to their algebraic connectivities when . This extends the results of Liu and Liu [Y. Liu, Y. Liu, The ordering of unicyclic graphs with the smallest algebraic connectivity, Discrete Math. 309 (2009) 4315–4325] and Guo [J.-M. Guo, A conjecture on the algebraic connectivity of connected graphs with fixed girth, Discrete Math. 308 (2008) 5702–5711]. [ABSTRACT FROM AUTHOR]

Abstract: The Laplacian spectral radius of a graph is the largest eigenvalue of the associated Laplacian matrix. In this paper, we determine those graphs which maximize the Laplacian spectral radius among all bipartite graphs with (edge-)connectivity at most . We also characterize graphs of order with cut-edges, having Laplacian spectral radius equal to . [Copyright &y& Elsevier]

The nullity η (G) of a (simple) graph G is the multiplicity of 0 as an eigenvalue of the adjacency matrix of G. It was shown by Ma et al. (2016) that for a connected graph G with n (G) vertices, e (G) edges and p (G) (≥ 1) pendant vertices, η (G) ≤ 2 c (G) + p (G) − 1 , where c (G) = e (G) − n (G) + θ (G) is the cyclomatic number of G , θ (G) being the number of connected components of G. In this paper connected graphs G and trees T that satisfy respectively the conditions η (G) = 2 c (G) + p (G) − 1 and η (T) = p (T) − 1 are characterized. Besides, we identify the matched and mismatched vertices in a tree T that satisfies η (T) = p (T) − 1 and characterize trees T that have a pendant vertex matched in T and satisfy η (T) = p (T) − 2. We obtain new sharp lower and upper bounds for a tree T with p (T) ≥ 3 , given in terms of p (T) and the numbers of two special kinds of internal paths in T. It is also proved that for any integer c ≥ 2 , the set of values attained by η (G) − n (G) + 2 m (G) , as G runs through all connected, leaf-free graphs G with cyclomatic number c , is { − c + 1 , − c + 2 , ... , 2 c − 3 , 2 c − 2 }. [ABSTRACT FROM AUTHOR]

By the well-known Perron–Frobenius Theorem [3] , for a connected graph G , its largest eigenvalue strictly increases when an edge is added. We are interested in how the other eigenvalues of a connected graph change when edges are added. Examples show that all cases are possible: increased, decreased, unchanged. In this paper, we consider the effect on the eigenvalues by suitably adding edges in particular families, say the family of connected graphs with clusters. By using the result, we also consider the effect on the energy by suitably adding edges to the graphs of the above families. [ABSTRACT FROM AUTHOR]

Let G be a simple connected graph and $S_{2}(G)$ be the sum of the two largest Laplacian eigenvalues of G. In this paper, we determine the bicyclic graph with maximum $S_{2}(G)$ among all bicyclic graphs of order n, which confirms the conjecture of Guan et al. (J. Inequal. Appl. 2014:242, 2014) for the case of bicyclic graphs. .. [ABSTRACT FROM AUTHOR]

Abstract: Let be the lollipop graph obtained by appending a g-cycle to a pendant vertex of a path on vertices. In 2002, Fallat, Kirkland and Pati proved that for and , . In this paper, we prove that for , for all n, where is the algebraic connectivity of . [Copyright &y& Elsevier]