A partition of connected graphs

Details A partition of connected graphs A partition of connected graphs

2005-05-09

arxiv.org/abs/math/0505155v1

Electronic J. Combinatorics 12, N1 (2005), 8pp

Mathematics

Combinatorics

8 pages

Scientific paper

We define an algorithm k which takes a connected graph G on a totally ordered vertex set and returns an increasing tree R (which is not necessarily a subtree of G). We characterize the set of graphs G such that k(G)=R. Because this set has a simple structure (it is isomorphic to a product of non-empty power sets), it is easy to evaluate certain graph invariants in terms of increasing trees. In particular, we prove that, up to sign, the coefficient of x^q in the chromatic polynomial of G is the number of increasing forests with q components that satisfy a condition that we call G-connectedness. We also find a bijection between increasing G-connected trees and broken circuit free subtrees of G.

Affiliated with

Also associated with

No associations

Rating

A partition of connected graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A partition of connected graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A partition of connected graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-312743