[PDF] [PDF] On the adjacency matrix of a block graph - Indico

[PDF] BIPARTITE GRAPHS OBTAINED FROM ADJACENCY MATRICES

thought of as the adjacency matrix of a bipartite graph B(G) of order 2n, where the rows and columns correspond to the bipartition of B(G) For agraph H, let k(H) 

[PDF] Solution (#1027) Let A be the adjacency matrix of a bipartite graph

Solution (#1027) Let A be the adjacency matrix of a bipartite graph with vertices v1, ,vn As the graph is bipartite we can partition the vertex set into disjoint 

[PDF] Graph Theory for Network Science - Jackson State University

A regular graph is a graph in which all vertices have the same degree Note that Adjacency Matrix of an A bipartite graph (or bigraph) is a network whose

[PDF] On the adjacency matrix of a block graph - Indico

The formula for the inverse of a bipartite graph with a unique perfect matching ( and the inverse of a nonsingular tree) follow as special cases Page 50 Conclusion

[PDF] EXPLOITING THE STRUCTURE OF BIPARTITE GRAPHS FOR

A powerful and widespread class of network analysis methods is based on algebraic graph theory, i e , representing graphs as square adjacency matrices

[PDF] Spectra of graphs

adjacency matrix A, that is, its set of eigenvalues together with their multiplic- ities The Laplace cency matrix of a bipartite graph has the form A = [ 0 B B⊤ 0 ]

[PDF] Spectra of Simple Graphs - Whitman College

13 mai 2013 · An example Bipartite graph on 6 vertices: 1 2 3 4 5 6 Figure 2 4 Bipartite Graph The general form for the adjacency matrix of a bipartite 

Matrices and α-Stable Bipartite Graphs - jucsorg

10 sept 2007 · The reduced adjacency matrix of a bipartite graph G = (A,B,E) (having A ∪ B = { a1, , am}∪{b1, , bn} as a vertex set, and E as an edge set), is

[PDF] bipartite graph adjacency matrix in r

[PDF] bipartite graph algorithm dfs

[PDF] bipartite graph definition with example

[PDF] bipartite graph example pdf

[PDF] bipartite graph worksheet

[PDF] bird on australian 50 cent coin

[PDF] birth rates in europe by country

[PDF] birthday reminder android app source code

[PDF] bis exchange rate index

[PDF] bit masking in c geeksforgeeks

[PDF] bitcoin pdf 2020

[PDF] bitcoin price

[PDF] bitcoin sovereignty through mathematics pdf

[PDF] bitwise and operators in c

[PDF] bitwise operators in c with examples

On the adjacency matrix of a block graph

R.B.Bapat

Indian Statistical Institute

New Delhi

This talk is primarily based on joint work with Souvik Roy. The later part contains related results and some recent work in progress with Ebrahim Ghorbani. Block

A block is a maximal subgraph with no cut-vertex.

Block graph

A block graph is a graph in which each block is a complete graph.

A characterization of trees

A tree is a block graph.

A connected graph is a tree if and only if each edge is a block.

A block graph generalizes:

(i) tree (ii) complete graph.

Motivation

The following classical results motivated the present work: A tree is nonsingular if and only if it has a perfect matching. When a tree is nonsingular, there is a formula for its inverse in terms of alternating paths.

Adjacency matrix of a complete graph

IfAis the adjacency matrix ofKn;then

detA= (1)n1(n1):

Adjacency matrix of a block graph

Consider the block graph

Adjacency matrix

A=0 B

BBBBBBBBB@0 1 1 1 0 0 0 0

1 0 1 1 0 0 0 0

1 1 0 1 0 0 0 0

1 1 1 0 1 1 1 1

0 0 0 1 0 1 1 1

0 0 0 1 1 0 1 1

0 0 0 1 1 1 0 1

0 0 0 1 1 1 1 01

C

CCCCCCCCCA

detA=X(11)(21); where the summation is over

014;025;1+2= 8:

detA= (41)(41) + (31)(51) = 17:

Theorem

LetGbe a block graph withnvertices. LetB1;:::;Bkbe the blocks ofGand letjV(Bi)j=ni;i= 1;:::;k:LetAbe the adjacency matrix ofG:Then detA= (1)nkX(11)(k1) where the summation is over allk-tuples (1;:::;k) of nonnegative integers satisfying the following conditions: (i)Pk i=1i=n (ii) for any nonemptyS f1;:::;kg; X i2S i jV(GS)j; whereGSis the subgraph induced by the blocks B i;i2S:

Nonsingular trees

CorollaryA tree is nonsingular if and only if it has a perfect matching.

Singular block graphs

Trees with no perfect matching are examples of singular block graphs. There are other examples. A singular block graph with an odd number of vertices: A singular block graph with an even number of vertices

A class of singular graphs

LetTbe a singular tree and letSV(T) be the set of vertices corresponding to a zero in the null vector. LetGbe the graph obtained fromTby attaching an arbitrary graph at each vertex inS:

ThenGis singular.

An open problem

Characterize nonsingular block graphs.

Adjacency matrix over GF(2)

LemmaLetGbe a graph withnvertices and letAbe the

adjacency matrix ofG:Ifnis odd then detAis even.

In particular,Ais singular over GF(2).

A reduction procedure

LetGbe a graph with blocksB1;:::;Bk:LetB1be pendant and letvbe the cut-vertex ofB1: (i) IfjV(B1)jis even, thenGis nonsingular if and only ifGnB1is nonsingular. (i) IfjV(B1)jis odd, thenGis nonsingular if and only ifGn(B1nv) is nonsingular.

Example

A=0 B

BBBBBBBBB@0 1 1 1 0 0 0 0

1 0 1 1 0 0 0 0

1 1 0 1 0 0 0 0

1 1 1 0 1 1 1 1

0 0 0 1 0 1 1 1

0 0 0 1 1 0 1 1

0 0 0 1 1 1 0 1

0 0 0 1 1 1 1 01

C

CCCCCCCCCA

Example

Using the previous result we conclude that this graph is singular: LemmaLetGbe a block graph with adjacency matrixA:Letvbe a vertex ofGsuch thatGnvhas at least two odd components. Then detAis an even integer. In particular,Ais singular over

GF(2).

Nonsingular block graphs over GF(2)

TheoremLetGbe a block graph and letAbe the adjacency matrix ofG:ThenAis nonsingular over GF(2) if and only if for

any vertexv;Gnvhas exactly one odd component.Corollary 1LetGbe a block graph withnvertices and letAbe

the adjacency matrix ofG:Ifnis odd, thenAis singular over GF(2).Corollary 2LetTbe a tree and letAbe the adjacency matrix of G:IfThas no perfect matching thenAis singular over GF(2).

Nonsingular block graphs over GF(2)

TheoremLetGbe a block graph and letAbe the adjacency matrix ofG:ThenAis nonsingular over GF(2) if and only if for

any vertexv;Gnvhas exactly one odd component.Corollary 1LetGbe a block graph withnvertices and letAbe

the adjacency matrix ofG:Ifnis odd, thenAis singular over GF(2).Corollary 2LetTbe a tree and letAbe the adjacency matrix of G:IfThas no perfect matching thenAis singular over GF(2).

Nonsingular block graphs over GF(2)

TheoremLetGbe a block graph and letAbe the adjacencyquotesdbs_dbs2.pdfusesText_3