Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #8006 > unrolled thread

on notation, MM', graph theory, incidence matrix product

Back to article view | Back to comp.programming

Contents

  on notation, MM', graph theory, incidence matrix product Daniel Bastos <dbastos@toledo.com> - 2017-09-16 11:26 -0300
    Re: on notation, MM', graph theory, incidence matrix product Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-09-16 16:39 +0100
      Re: on notation, MM', graph theory, incidence matrix product Daniel Bastos <dbastos@toledo.com> - 2017-09-17 07:51 -0300

#8006 — on notation, MM', graph theory, incidence matrix product

Problem.  Show that if G is simple, the entries on the diagonals of both
MM' and A^2 are the degrees of the vertices of G.

I don't understand what is meant by MM'.  M is the incidence matrix of
graph G.  By looking at section 1.4, subgraphs, I take that M' must be
the incidence matrix of some subgraph induced by M, but M is a matrix,
so I'm puzzled.  AFAIK, I need a set of vertices of a set of edges to
induce a subgraph.

I appreciate a clarification on the book's notation.  Thank you!

This is problem 1.5.2 in ``Graph theory with applications'' by
J.A. Bondy and U.S.R. Murty, Department of Combinatorics and
Optimization, University of Waterloo, Ontario, Canada.  North-Holland,
fifth printing, 1982.  ISBN: 0-444-19451-7.

[toc] | [next] | [standalone]

#8008

Daniel Bastos <dbastos@toledo.com> writes:

> Problem.  Show that if G is simple, the entries on the diagonals of both
> MM' and A^2 are the degrees of the vertices of G.
>
> I don't understand what is meant by MM'.  M is the incidence matrix of
> graph G.  By looking at section 1.4, subgraphs, I take that M' must be
> the incidence matrix of some subgraph induced by M,

No.  The notation is confusing but ' is often used for different things
in different places.

> but M is a matrix,
> so I'm puzzled.  AFAIK, I need a set of vertices of a set of edges to
> induce a subgraph.

You are right.  M is a matrix and the ' just means normal matrix
transposition.  M is (in general) a rectangular v x e matrix so it can
only be multiplied by an e x v matrix such as the transpose.  The
incidence matrix of any subgraph would not be the right size.  In effect
you have to deduce the meaning from the only thing that could make
sense.

> I appreciate a clarification on the book's notation.  Thank you!

The summary of synbols at the end gives R' as the transpose of R.  It's
a shame it was used with that meaning right after some text that used V'
and E' simply as a modifier to mean some subset of V or E.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#8010

Ben Bacarisse <ben.usenet@bsb.me.uk> writes:

> Daniel Bastos <dbastos@toledo.com> writes:
>
>> Problem.  Show that if G is simple, the entries on the diagonals of both
>> MM' and A^2 are the degrees of the vertices of G.
>>
>> I don't understand what is meant by MM'.  M is the incidence matrix of
>> graph G.  By looking at section 1.4, subgraphs, I take that M' must be
>> the incidence matrix of some subgraph induced by M,
>
> No.  The notation is confusing but ' is often used for different things
> in different places.
>
>> but M is a matrix,
>> so I'm puzzled.  AFAIK, I need a set of vertices of a set of edges to
>> induce a subgraph.
>
> You are right.  M is a matrix and the ' just means normal matrix
> transposition.  M is (in general) a rectangular v x e matrix so it can
> only be multiplied by an e x v matrix such as the transpose.  The
> incidence matrix of any subgraph would not be the right size.  In effect
> you have to deduce the meaning from the only thing that could make
> sense.

I did happen to consider ' as matrix transposition, but then I
(incorrectly) found a counterexample to the claim so I thought I was
totally off.  The counterexample I found was for a nonsimple graph.

>> I appreciate a clarification on the book's notation.  Thank you!
>
> The summary of synbols at the end gives R' as the transpose of R.  It's
> a shame it was used with that meaning right after some text that used V'
> and E' simply as a modifier to mean some subset of V or E.

Yes! :-) Thanks very much!

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming

csiph-web