Determinant of the Laplacian Matrix of a Weighted Directed Graph

The notion of weighted directed graph is a generalization of mixed graphs. In this article a formula for the determinant of the Laplacian matrix of a weighted directed graph is obtained. It is a generalization of the formula for the determinant of the Lap

  • PDF / 249,213 Bytes
  • 6 Pages / 439.37 x 666.142 pts Page_size
  • 51 Downloads / 213 Views

DOWNLOAD

REPORT


Abstract The notion of weighted directed graph is a generalization of mixed graphs. In this article a formula for the determinant of the Laplacian matrix of a weighted directed graph is obtained. It is a generalization of the formula for the determinant of the Laplacian matrix of a mixed graph obtained by Bapat et al. (Linear Multilinear Algebra 46:299–312, 1999). Keywords Laplacian matrix · Mixed graph · Weighted directed graph · 3-Colored digraph · Essential spanning subgraph Mathematics Subject Classification (2010) 05C50 · 05C05 · 15A18

1 Introduction Throughout this article all our graphs are simple. All our directed graphs have simple underlying undirected graphs. At times we use V (G) (resp. E(G)) to denote the set of vertices (resp. edges) of a graph G (directed or undirected). In the absence of any specification, V (G) is assumed to be the set {1, 2, . . . , n}. We write (i, j ) ∈ E(G) to mean the existence of the directed edge from a vertex i to a vertex j . Sometimes it is convenient to denote (i, j ) ∈ E(G) by i  j . Throughout this √ article, ı = −1. Definition 1 (Bapat et al. [1]) Let G be a directed graph. With each edge (i, j ) in E(G), we associate a complex number wij of unit absolute value and nonnegative imaginary part. We call it the weight of that edge. A directed graph G with such a weight function w is called a weighted directed graph. The adjacency matrix A(G) of G is the matrix with ij th entry

D. Kalita (B) Department of Mathematical Sciences, Tezpur University, Napam, Sonitpur, Assam 784028, India e-mail: [email protected] R.B. Bapat et al. (eds.), Combinatorial Matrix Theory and Generalized Inverses of Matrices, DOI 10.1007/978-81-322-1053-5_5, © Springer India 2013

57

58

D. Kalita

aij =

⎧ ⎪ ⎨ wij ⎪ ⎩

wj i

0

if i  j, if j  i, otherwise.

Let G be a weighted directed graph. In defining subgraph, walk, path, component, connectedness, and degree of a vertex in G, we focus only on the underlying unweighted undirected graph of G. Thus the degree di of a vertex i in a weighted directed graph may be viewed as the sum of absolute values of the weights of the edges incident with vertex i. Definition 2 (Bapat et al. [1]) Let G be a weighted directed graph. The Laplacian matrix L(G) of G is defined as the matrix D(G) − A(G), where D(G) is the diagonal matrix with di as the ith diagonal entry. Definition 3 (Bapat et al. [1]) The vertex edge incidence matrix M = M(G) = [mi,e ] of a weighted directed graph G is defined as the matrix with rows labeled by the vertices and columns labeled by the edges in G satisfying ⎧ if e = (i, j ) for some vertex j, ⎪ ⎨1 mi,e = −wij if e = (j, i) for some vertex j, ⎪ ⎩ 0 otherwise. Example 1 Consider the weighted directed graph G as shown below. Weights of the edges are written beside them. The vertex edge incidence matrix M(G) of G is supplied.

A mixed graph is a graph with some directed and some undirected edges. Let G be a weighted directed graph. If the weights of the edges in G are ±1, then viewing the edges of weight 1 as directed and the edges