Let
G be a graph on
n vertices. Its Laplacian matrix is the
n-by-
n matrix
L(
G)
D(
G)−
A(
G), where
A(G) is the familiar (0,1) adjacency matrix, and
D(G) is the diagonal matrix of vertex degrees. ...This is primarily an expository article surveying some of the many results known for Laplacian matrices. Its six sections are: Introduction, The Spectrum, The Algebraic Connectivity, Congruence and Equivalence, Chemical Applications, and Immanants.
Laplacian graph eigenvectors Merris, Russell
Linear algebra and its applications,
1998, Letnik:
278, Številka:
1
Journal Article
Recenzirano
Odprti dostop
If
G is a graph, its Laplacian is the difference of the diagonal matrix of its vertex degrees and its adjacency matrix. The main thrust of the present article is to prove several Laplacian ...eigenvector “principles” which in certain cases can be used to deduce the effect on the spectrum of contracting, adding or deleting edges and/or of coalescing vertices. One application is the construction of two isospectral graphs on 11 vertices having different degree sequences, only one of which is bipartite, and only one of which is decomposable.
Let
G = (
V,
E) be a graph on
n vertices. Denote by
d(
v) the degree of
v ∈
V and by
m(
v) the average of the degrees of the vertices of
G adjacent to
v. Then
b(
G) = max{
m(
v) +
d(
v):
v ∈
V} is an ...upper bound for the Laplacian spectral radius of
G; hence,
n −
b(
G
C) is a lower bound for the algebraic connectivity of
G in terms of the vertex degrees of its complement.
A graph that can be constructed from isolated vertices by the operations of union and complement is decomposable. Every decomposable graph is Laplacian integral. i.e., its Laplacian spectrum consists ...entirely of integers. An indecomposable graph is not decomposable. The main purpose of this note is to demonstrate the existence of infinitely many indecomposable Laplacian integral graphs.
Split graphs Merris, Russell
European journal of combinatorics,
05/2003, Letnik:
24, Številka:
4
Journal Article
Recenzirano
Odprti dostop
The main topics of this article are split graphs, their degree sequences, and the place of these “split partitions” at the top of the partially ordered set of graphic partitions. One application is ...that threshold covered partitions are unigraphic.
A survey of graph laplacians Merris, Russell
Linear & multilinear algebra,
19/7/1/, Letnik:
39, Številka:
1-2
Journal Article
Recenzirano
Let G be a graph on n vertices. Its Laplacian is the n-by-n matrix L(G)−D(G)−A(G), where D(G) is the diagonal matrix of vertex degrees and A(G) is the (0,1)-adjacency matrix of G. This article ...surveys recent results on graph Laplacians.
Something between an expository note and an extended research problem, this article is an invitation to expand the existing literature on a family of graph invariants rooted in linear and multilinear ...algebra. There are a variety of ways to assign a real
n×
n matrix
K(
G) to each
n-vertex graph
G, so that
G and
H are isomorphic if and only if
K(
G) and
K(
H) are permutation similar. It follows that
G and
H are isomorphic only if
K(
G) and
K(
H) are similar, i.e., that similarity invariants of
K(
G) are graph theoretic invariants of
G, an observation that helps to explain the enormous literature on
spectral graph theory. The focus of this article is the
permutation part, i.e., on matrix functions that are preserved under permutation similarity if not under all similarity.
An integer sequence (
d) = (
d
1,
d
2,…,
d
n
) is
graphic if there is a graph whose degree sequence is (
d). A graph
G is
maximal if its degree sequence is majorized by no other graphic sequence. The ...Laplacian matrix of
G is
L(
G) =
D(
G) -
A(
G), where
D(G) is the diagonal matrix of vertex degrees and
A(G) is the (0,1) adjacency matrix. The article contains an explicit (algorithmic) construction of all maximal graphs, from which it follows, e.g., that, apart from 0, the Laplacian spectrum of a maximal graph is the conjugate of its degree sequence.
PDF
