The perturbed Laplacian matrix of a graph G is defined as DL = D−A, where D is any diagonal matrix and A is a weighted adjacency matrix of G. We develop a Fiedler-like theory for this matrix, leading to results that are of the same type as those obtained with the algebraic connectivity of a graph. We show a monotonicity theorem for the harmonic eigenfunction corresponding to the second smallest eigenvalue of the perturbed Laplacian matrix over the points of articulation of a graph. Furthermore, we use the notion of Perron component for the perturbed Laplacian matrix of a graph and show how its second smallest eigenvalue can be characterized using this definition., Israel Rocha, Vilmar Trevisan., and Obsahuje seznam literatury
Let $G$ be a $k$-connected graph with $k \ge 2$. A hinge is a subset of $k$ vertices whose deletion from $G$ yields a disconnected graph. We consider the algebraic connectivity and Fiedler vectors of such graphs, paying special attention to the signs of the entries in Fiedler vectors corresponding to vertices in a hinge, and to vertices in the connected components at a hinge. The results extend those in Fiedler's papers Algebraic connectivity of graphs (1973), A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory (1975), and Kirkland and Fallat's paper Perron Components and Algebraic Connectivity for Weighted Graphs (1998).
A total dominating set in a graph $G$ is a subset $X$ of $V(G)$ such that each vertex of $V(G)$ is adjacent to at least one vertex of $X$. The total domination number of $G$ is the minimum cardinality of a total dominating set. A function $f\colon V(G)\rightarrow \{-1,1\}$ is a signed dominating function (SDF) if the sum of its function values over any closed neighborhood is at least one. The weight of an SDF is the sum of its function values over all vertices. The signed domination number of $G$ is the minimum weight of an SDF on $G$. In this paper we present several upper bounds on the algebraic connectivity of a connected graph in terms of the total domination and signed domination numbers of the graph. Also, we give lower bounds on the Laplacian spectral radius of a connected graph in terms of the signed domination number of the graph.
Let $G$ be a connected simple graph on $n$ vertices. The Laplacian index of $G$, namely, the greatest Laplacian eigenvalue of $G$, is well known to be bounded above by $n$. In this paper, we give structural characterizations for graphs $G$ with the largest Laplacian index $n$. Regular graphs, Hamiltonian graphs and planar graphs with the largest Laplacian index are investigated. We present a necessary and sufficient condition on $n$ and $k$ for the existence of a $k$-regular graph $G$ of order $n$ with the largest Laplacian index $n$. We prove that for a graph $G$ of order $n \geq 3$ with the largest Laplacian index $n$, $G$ is Hamiltonian if $G$ is regular or its maximum vertex degree is $\triangle (G)=n/2$. Moreover, we obtain some useful inequalities concerning the Laplacian index and the algebraic connectivity which produce miscellaneous related results.
Let µ_{n-1}(G) be the algebraic connectivity, and let µ_{1}(G) be the Laplacian spectral radius of a k-connected graph G with n vertices and m edges. In this paper, we prove that {\mu _{n - 1}}(G) \geqslant \frac{{2n{k^2}}}{{(n(n - 1) - 2m)(n + k - 2) + 2{k^2}}} , with equality if and only if G is the complete graph Kn or Kn − e. Moreover, if G is non-regular, then {\mu _1}(G) < 2\Delta - \frac{{2(n\Delta - 2m){k^2}}}{{2(n\Delta - 2m)({n^2} - 2n + 2k) + n{k^2}}} , where ▵ stands for the maximum degree of G. Remark that in some cases, these two inequalities improve some previously known results., Xiaodan Chen, Yaoping Hou., and Obsahuje seznam literatury