The imbalance of an edge e = {u, v} in a graph is defined as i(e) = |d(u)−d(v)|, where d(·) is the vertex degree. The irregularity I(G) of G is then defined as the sum of imbalances over all edges of G. This concept was introduced by Albertson who proved that I(G)\leqslant 4n^{3}/27 (where n = |V(G)|) and obtained stronger bounds for bipartite and triangle-free graphs. Since then a number of additional bounds were given by various authors. In this paper we prove a new upper bound, which improves a bound found by Zhou and Luo in 2008. Our bound involves the Laplacian spectral radius λ., Felix Goldberg., and Obsahuje seznam literatury
Let $G$ be a simple connected graph of order $n$ with degree sequence $(d_1,d_2,\ldots ,d_n)$. Denote $(^\alpha t)_i = \sum \nolimits _{j\colon i \sim j} {d_j^\alpha }$, $(^\alpha m)_i = {(^\alpha t)_i }/{d_i^\alpha }$ and $(^\alpha N)_i = \sum \nolimits _{j\colon i \sim j} {(^\alpha t)_j }$, where $\alpha $ is a real number. Denote by $\lambda _1(G)$ and $\mu _1(G)$ the spectral radius of the adjacency matrix and the Laplacian matrix of $G$, respectively. In this paper, we present some upper and lower bounds of $\lambda _1(G)$ and $\mu _1(G)$ in terms of $(^\alpha t)_i $, $(^\alpha m)_i $ and $(^\alpha N)_i $. Furthermore, we also characterize some extreme graphs which attain these upper bounds. These results theoretically improve and generalize some known results.
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.
In this paper we consider the following problem: Over the class of all simple connected unicyclic graphs on $n$ vertices with girth $g$ ($n$, $g$ being fixed), which graph minimizes the Laplacian spectral radius? Let $U_{n,g}$ be the lollipop graph obtained by appending a pendent vertex of a path on $n-g$ $(n> g)$ vertices to a vertex of a cycle on $g\geq 3$ vertices. We prove that the graph $U_{n,g}$ uniquely minimizes the Laplacian spectral radius for $n\geq 2g-1$ when $g$ is even and for $n\geq 3g-1$ when $g$ is odd.
In this paper we present some theoretical results about the irreducibility of the Laplacian matrix ordered by the Reverse Cuthill-McKee (RCM) algorithm. We consider undirected graphs with no loops consisting of some connected components. RCM is a well-known scheme for numbering the nodes of a network in such a way that the corresponding adjacency matrix has a narrow bandwidth. Inspired by some properties of the eigenvectors of a Laplacian matrix, we derive some properties based on row sums of a Laplacian matrix that was reordered by the RCM algorithm. One of the theoretical results serves as a basis for writing an easy MATLAB code to detect connected components, by using the function “symrcm” of MATLAB. Some examples illustrate the theoretical results., Francisco Pedroche, Miguel Rebollo, Carlos Carrascosa, Alberto Palomares., and Obsahuje seznam literatury
The Laplacian, signless Laplacian and normalized Laplacian characteristic polynomials of a graph are the characteristic polynomials of its Laplacian matrix, signless Laplacian matrix and normalized Laplacian matrix, respectively. In this paper, we mainly derive six reduction procedures on the Laplacian, signless Laplacian and normalized Laplacian characteristic polynomials of a graph which can be used to construct larger Laplacian, signless Laplacian and normalized Laplacian cospectral graphs, respectively.
In this paper, the effects on the signless Laplacian spectral radius of a graph are studied when some operations, such as edge moving, edge subdividing, are applied to the graph. Moreover, the largest signless Laplacian spectral radius among the all unicyclic graphs with $n$ vertices and $k$ pendant vertices is identified. Furthermore, we determine the graphs with the largest Laplacian spectral radii among the all unicyclic graphs and bicyclic graphs with $n$ vertices and $k$ pendant vertices, respectively.