Mathematics – Combinatorics
Scientific paper
2007-12-12
Adv. in Appl. Math. 43 (2009), no. 1, pp. 46-74
Mathematics
Combinatorics
Work presented at the Ottawa-Carleton Discrete Mathematics Workshop, May 25-26, 2007 and at the Seminaire Lotharingien de Comb
Scientific paper
10.1016/j.aam.2009.01.002
We adapt the classical 3-decomposition of any 2-connected graph to the case of simple graphs (no loops or multiple edges). By analogy with the block-cutpoint tree of a connected graph, we deduce from this decomposition a bicolored tree tc(g) associated with any 2-connected graph g, whose white vertices are the 3-components of g (3-connected components or polygons) and whose black vertices are bonds linking together these 3-components, arising from separating pairs of vertices of g. Two fundamental relationships on graphs and networks follow from this construction. The first one is a dissymmetry theorem which leads to the expression of the class B=B(F) of 2-connected graphs, all of whose 3-connected components belong to a given class F of 3-connected graphs, in terms of various rootings of B. The second one is a functional equation which characterizes the corresponding class R=R(F) of two-pole networks all of whose 3-connected components are in F. All the rootings of B are then expressed in terms of F and R. There follow corresponding identities for all the associated series, in particular the edge index series. Numerous enumerative consequences are discussed.
Gagarin Andrei
Labelle Gilbert
Leroux Pierre
Walsh Timothy
No associations
LandOfFree
Two-connected graphs with prescribed three-connected components 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 Two-connected graphs with prescribed three-connected components, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Two-connected graphs with prescribed three-connected components will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-660975