9512.net
甜梦文库
当前位置:首页 >> >>

Article 04.3.1 The Number of Labelled k-Arch Graphs


1

2 3 6

47 23 11

Journal of Integer Sequences, Vol. 7 (2004), Article 04.3.1

The Number of Labelled k -Arch Graphs
C? edric Lamathe LORIA - INRIA Lorraine Campus Scienti?que, B.P. 239 54506 Vandoeuvre-l` es-Nancy Cedex, France lamathe@loria.fr
Abstract In this note, we deal with k -arch graphs, a generalization of trees, which contain k -trees as a subclass. We show that the number of vertex-labelled k -arch graphs with n?k?1 n vertices, for a ?xed integer k ≥ 1, is n . As far as we know, this is a new k integer sequence. We establish this result with a one-to-one correspondence relating k -arch graphs and words whose letters are k -subsets of the vertex set. This bijection generalises the well-known Pr¨ ufer code for trees. We also recover Cayley’s formula n ? 2 n that counts the number of labelled trees.

1

Introduction

We recursively de?ne the class of k -arch graphs, for k ≥ 1, as the smallest class of simple graphs such that: 1. a (k ? 1)-simplex (i.e., a complete graph on k vertices) is a k -arch graph; 2. if a simple graph G has a vertex v of degree k such that the graph G ? {v } obtained from G by removing v and its incident edges is a k -arch graph, then G is a k -arch graph. Figure 1 shows an unlabelled 2-arch graph (we simply say arch graph in this case) and a vertex-labelled 2-arch graph, each one built over 12 vertices. Note that, when k = 1, 1-arch graphs coincide with (Cayley) trees. In a constructive way, to build a k -arch graph of n + 1 vertices from one on n vertices, we have to choose k vertices and join the new vertex to these selected vertices. The term arch evokes attaching the new vertex over the k chosen vertices. There are few papers about k -arch graphs, apart from [18], where these graphs seem to appear, and [11]. However, there is an abundant literature about a subclass of k -arch 1

4 1 8

5

9 2 6 3 7 11 10 12

a)

b)

Figure 1: Arch graphs on 12 vertices a) unlabelled, b) vertex-labelled. graphs, called k -trees, studied since the later 1960’s. The essential di?erence between k -trees and k -arch graphs lie in the fact that for k -trees, we assume that the vertex v is attached to k mutually adjacent vertices (that is, it forms a complete graph on k + 1 vertices). For instance, see [4, 13] for the labelled enumeration of k -trees, and [3, 14] for the particular case k = 2. Harary and Palmer [7] treat the unlabelled enumeration as well as Fowler et al. [6], who provide in addition asymptotic formulas. We also mention [8, 5] for the enumeration of generalizations of 2-trees and [10], where various specializations of 2-trees are enumerated. Finally, Labelle et al. [9] propose a classi?cation of outerplanar 2-trees according to their symmetries. Although k -trees have been extensively studied, unlabelled enumeration of these structures is still an open problem. Apart from enumerative aspects of 2-trees, Leclerc and Makarenkov [12] give a correspondence between tree functions and 2-trees in the framework of tree metrics and tree dissimilarities (see [1, 2]). In [18, 11], k -arch graphs are de?ned as maximal kd-acyclic graphs, where a graph is said kd-acyclic, if it contains no kd-cycle (see [11], de?nition 3.1). Todd shows that this de?nition is equivalent to the recursive one given above. Leclerc uses valuated arch graphs (that is, arch graph with valuated edges) to encode tree distances or tree functions (see [1, 2]). We recall that the number of labelled k -trees over n vertices is given by ([4, 13]) ak n = n (k (n ? k ) + 1)n?k?2 . k (1)

When k = 1, we recover the well-known Cayley formula an = nn?2 counting labelled (Cayley) trees. The aim of this note is to obtain the number of labelled k -arch graphs. We show this number is n?k?1 n . k To achieve our goal, we propose in Section 2 a one-to-one correspondence between k -arch graphs on n vertices and words of length n ? k ? 1 whose letters are k -subsets of the set of 2

vertex labels. This correspondence generalizes the Pr¨ ufer code for trees ([15]).

2

The number of labelled k -arch graphs

In this section, we establish a formula giving the number of labelled k -arch graphs, for k ≥ 1. We prove this formula using a bijective argument based on a generalization of the Pr¨ ufer code for vertex-labelled Cayley trees ([15]) which has been generalized for k -trees ([16]). Note that formula (2) ?rst appear (without proof) in the conclusion of [10]. We call leaf of a k -arch graph, a vertex of degree k . For instance, in Figure 1 b), there are four leaves, respectively labelled 2,3,4,9. This de?nition of leaf is legitimate since, for the special case k = 1, a vertex of degree one in a Cayley tree is a leaf, in the common sense of graph theory.
k Proposition 1 Let k ≥ 1 be a ?xed integer. Then, the number Gn of k -arch graphs over n labelled vertices, for n > k , is given by

k Gn =

n k

n?k?1

and

k Gk = 1.

(2)

such that

Proof. We construct a one-to-one correspondence between k -arch graphs on n labelled vertices and words w = w1 w2 . . . wn?k?1 of length n ? k ? 1 where each wi is a (valid) k -letter of the following form: ? ? v i1 ? vi ? ? 2? (3) ? . ? ? . . ? v ik 1. for all 1 ≤ j ≤ k , 1 ≤ ij ≤ n; 2. for all 1 ≤ j ≤ n, vj is a vertex of the k -arch graph; 3. i1 < i2 < · · · < ik .

Such words are called valid. We implicitly assume that an order is given on the labels, i.e., v1 < v2 < . . . < vn . The one-to-one correspondence works by successive leaf deletions. Let g be a k -arch graph on n vertices with vertex set V = {v1 , v2 , . . . , vn }. At the ?rst step, we choose the leaf with the smallest label in g , we remove it from g as well as its incident edges and form a k -letter with its adjacent vertices by ordering them in increasing order. The fact that the degree of a leaf is k and the vertex ordering ensure we can always form a unique valid k -letter. After the ?rst leaf deletion, we obtain a k -arch graph with n ? 1 vertices and we repeat the ?rst step. Repeating this step n ? k ? 1 times, we get a valid word of length n ? k ? 1. Observe that after the last step, the k -arch graph g becomes a single k ? 1-simplex,

3

that is, a complete graph on k vertices. For instance, if we apply this construction to the arch graph of Figure 1 b), we obtain the following valid word of length 9: 1 7 1 8 7 5 8 8 10 6 11 6 11 11 12 10 7 11 . (4)

Conversely, given a valid word w = w1 w2 . . . wn?k?1 of length n ? k ? 1, we want to construct a k -arch graph with n labelled vertices. Together with w, we use a dynamic subset L of the vertex set V , that is, a subset with evolving entries and size. At the beginning, we ?ll L with all vertices not appearing in w and we extend w by appending a copy of the last k -letter, wn?k?1 , at the end of w. We also denote w this extended word w := w||wn?k?1 = w1 w2 . . . wn?k?1 wn?k?1 . For instance, according to the labelled k -arch graph of Figure 1 b), we obtain L = {2, 3, 4, 9} and w becomes 1 7 1 8 7 5 8 8 10 10 . 6 11 6 11 11 12 10 7 11 11 We remove the smallest element of L and join it to every entry of the ?rst k -letter (w 1 ) of w. We then delete w1 from w and still call w this reduced word. We update L by adding every vertex vi ∈ w1 not appearing in the remaining letters of w. We repeat the above recursive step with the word w = w2 . . . wn?k?1 wn?k?1 , and so on until we reach the empty word, keeping at each step the connected component created. To end the converse map, we have to connect together the k vertices of the last k -letter wn?k?1 of w. We have to verify that we obtain a connected graph which is a k -arch graph corresponding to the word w when the leaf deletion algorithm is applied. It is quite straightforward using a recursive argument, as the reader can check. Figure 2 shows a complete example of the reverse map for a labelled arch graph of six vertices. Remark 1 It is interesting to note that, for k = 1, formula (2) remains valid. Indeed, this formula becomes Cayley formula (an = nn?2 ) enumerating trees with n labelled vertices. Remark 2 The converse map constructed in the proof of Proposition 1 induces easily an algorithm of random generation of labelled k -arch graphs by means of valid words.

3

Conclusion

The following table gives the ?rst few values of the number of k -arch graphs over n labelled vertices, for k from 1 up to 7, and for n from k up to 10. Only the ?rst line of this table (corresponding to Cayley formula an = nn?2 ) is listed in the on-line Encyclopedia of Integer Sequences [17] (sequence A000272). 4

5

6

Step 1

w=

(

3 1 4 4 6 4 6 6 6

)

L={2,5}

Step 2

w=

(

1 4 4 4 6 6 6

)
1

L= {3,5}

4

1

2

3

2 3 1 4 6 4 6

4

2

w=

(

)
4 4 6 6 L= {1,5}

3

3

Step 3

w=

( )

Step 4

w=

( )
4 6 6

L={5,6}

Step 5

w=

()

L={6}

6

5

5

6

4 4 1 2 3 3

1

4 2

1

2

3

Figure 2: Illustration of the reverse map. In this note, we showed by a bijective way that the number of labelled k -arch graphs is given by a new integer sequence. The class of k -arch graphs are a natural multidimensional generalization of trees, encompassing k -trees. To go further in the study of k -arch graphs, we have to wonder about the unlabelled enumeration of these graphs. Unfortunately, no result is known about the unlabelled enumeration of both k -arch graphs and k -trees. k \n 1 2 3 4 5 6 7

1 1 -

2 1 1 -

3 4 3 1 1 16 6 1 1 -

5 125 100 10 1 1 -

6 1296 3375 400 15 1 1 -

7 16807 194481 42875 1225 21 1 1

8 262144 17210368 9834496 343000 3136 28 1

9 4782969 2176782336 4182119424 252047376 2000376 7056 36

10 100000000 373669453125 2985984000000 408410100000 4032758016 9261000 14400

k Table 1: Values of Gn , for 1 ≤ k ≤ 7 and k ≤ n ≤ 10.

5

4

Acknowledgments

We greatly thank Bruno Leclerc for his presentation of k -arch graphs in a Montreal seminar (LaCIM seminar, Universit? e du Qu? ebec a ` Montr? eal) and Pierre Leroux for useful discussions.

References
[1] J. P. Barth? elemy et A. Gu? enoche, Les Arbres et les Repr? esentations des Proximit? es, Masson, 1988. [2] J. P. Barth? elemy and A. Gu? enoche, Trees and Proximity Representations, WileyInterscience Series in Discrete Mathematics and Optimization, 1991. [3] L. W. Beineke and J. W. Moon, Several proofs of the number of labeled 2-dimensional trees, in F. Harary ed., Proof Techniques in Graph Theory, Academic Press, 1969, pp. 11–20. [4] L. W. Beineke and R. Pippert, The number of labeled k -dimensional trees, J. Combin. Theory 6 (1969), 200–205. [5] M. Bousquet and C. Lamathe, Enumeration of solid 2-trees, in Proceedings of the 14 th international conference Formal Power Series and Algebraic Combinatorics (FPSAC’02), 2002, pp. 133–147. [6] T. Fowler, I. Gessel, G. Labelle, P. Leroux, The speci?cation of 2-trees, Adv. in Appl. Math. 28 (2002), 145–168. [7] F. Harary and E. Palmer, Graphical Enumeration, Academic Press, 1973. [8] G. Labelle, C. Lamathe and P. Leroux, Labelled and unlabelled enumeration of k -gonal 2-trees, J. Combin. Theory Ser. A 106 (2004), 193–219. [9] G. Labelle, C. Lamathe and P. Leroux, A classi?cation of plane and planar 2-trees, Theoret. Comput. Sci. 307 (2003), 337–363. [10] C. Lamathe, Sp? eci?cation de classes de structures arborescentes, Ph.D. dissertation, Universit? e du Qu? ebec a ` Montr? eal, (2003). [11] B. Leclerc, Graphes d’arches, Math. & Sci. humaines 157 (2002), 27–48. [12] B. Leclerc and V. Makarenkov, On some relations between 2-trees and tree metrics, Discrete Math. 192 (1998), 223–249. [13] J. W. Moon, The number of labeled k -trees, J. Combin. Theory 6 (1969), 196–199. [14] E. Palmer, On the number of labeled 2-trees, J. Combin. Theory 6 (1969), 206–207. [15] H. Pr¨ ufer, Neuer Beweis eines Satzes u ¨ber Permutationen, Arch. Math. Phys. 27 (1918), 742–744. 6

[16] C. R? enyi and A. R? enyi, The Pr¨ ufer code for k -trees, in Combinatoral theory and it’s applications (Proc. Colloq. Balatonf¨ ured, 1969), North-Holland, 1970, pp. 945–971. [17] N. J. A. Sloane and S. Plou?e, The Encyclopedia of Integer Sequences, Academic Press, 1995. http://www.research.att.com/?njas/sequences [18] P. Todd, A k -tree generalization that characterizes consistency of dimensioned engineering drawings, SIAM J. Disc. Math. 2 (1989), 255–261.

2000 Mathematics Subject Classi?cation: Primary 05A15, 05C30; Secondary 05A10. Keywords: k -arch graphs, Pr¨ ufer code, generalization of trees. (Concerned with sequences A000272, A098721, A098721, A098723 and A098724.)

Received December 22 2003; revised version received July 1 2004. Published in Journal of Integer Sequences, August 2 2004. Minor revision (to add new sequences), March 16 2005. Return to Journal of Integer Sequences home page.

7



更多相关文章:
Article 04.3.1 The Number of Labelled k-Arch Graphs.pdf
Article 04.3.1 The Number of Labelled k-Arch Graphs_专业资料。In this note, we deal with k-arch graphs, a generalization of trees, which contain ...
The Number of Labelled k-Arch Graphs.unkown
7 (2004), 3 Article 04.3.1 47 6 23 11 The Number of Labelled k-Arch Graphs Cedric Lamathe LORIA - INRIA Lorraine Campus Scientifique, B.P...
The Number of Labelled k-Arch Graphs.pdf
We show that the number of vertex-labelled k-arch graphs with n?k?1 ...Article 04.3.1 The Num... 暂无评价 7页 免费 On the Haj'os number o...
Towards Local Termination in Labelled K t 4 Deduction.pdf
Towards Local Termination in Labelled K t 4 ...g Where, if is the number of 3 subformulae ...A This article was typeset using the L TEX ...
On heights of monotonically labelled binary trees.pdf
(1.3) In the case of ordinary binary trees ( k = 1 ), it is well...cant contribution to the total number of monotonically 2-labelled binary ...
ffl (single rooted) Directed (labelled) Acylic Graphs (DAGs) ....pdf
ffl (single rooted) Directed (labelled) Acylic Graphs (DAGs) ffl Finite State Automata (FSA_专业资料。Feature Structures (FSs) are used in many com...
Global learning of labelled dependency trees.pdf
Global learning of labelled dependency trees_专业...ExD Atr_M Apos ExD_M Coord_M ExD_M AuxK ?...nite and inde?nite articles under one common fp...
15n-labelled proteins by....pdf
2006 FEBS 15 N-labelled proteins by cell-free synthesis K. Ozawa et al. Fig. 1. Combinatorial isotope labelling scheme. Oval symbols identify the 15N...
Synthesis of ferrocene-labelled 2-aminopyrimidine derivatives....pdf
Synthesis of ferrocene-labelled 2-aminopyrimidine derivatives_化学_自然科学_专业资料。Monatsh Chem DOI 10.1007/s00706-014-1299-1 ORIGINAL PAPER Synthesis ...
Some results for monotonically labelled simply generated ....pdf
For integer sequences (?k )k≥0 , the quantities Tn can be considered as the number of different {1, . . . , r}-labelled size-n trees of Tr...
Empirical Validation of Hand-labelled Nuclear Accent Patterns....pdf
Empirical Validation of Hand-labelled Nuclear ...(a) H* H% 0.5 0.3 0.1 -0.1 -0.3 ...English pronunciation models: a changing scene, K...
Synthesis of carbon-14 labelled midazolam.pdf
Synthesis of carbon-14 labelled midazolam_能源/化工_工程科技_专业资料。咪达唑仑,药物合成 Research Article Received 21 January 2009, Revised 7 May 2009, ...
...of Flow Labelled IPv4 on ATM Data Links Ipsilon Version 1.....pdf
al. Informational [Page 2] RFC 1954 Flow Labelled IPv4 on ATM May 1996 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 ...
An extremal problem on labelled directed trees and ....pdf
An extremal problem on labelled directed trees ...which the system of keys is exactly K[1, 3]...Let Kn denote the complete k-uniform hypergraph....
A labelled deduction system with Curry-Howard terms for ....pdf
Huet, K. G., and P.-M. C., \The Coq ...0 8-E 1 2 Induction over the natural numbers....s(1(s 3 Figure 1: The labelled deduction ...
Preparation and biological evaluation of 99Tc m-labelled ....pdf
Preparation and biological evaluation of 99Tc m-labelled fatty acids_专业资料...(O3DAF eeosre omamc.ersl hwdtatoC)I AC1wrbevdinrleT utsoe tw . 1n...
The structure and labelled enumeration of K3,3-subdivision-....unkown
The structure and labelled enumeration of K3,3-subdivision-free projective-planar graphs Andrei Gagarin, Gilbert Labelle and Pierre Leroux Laboratoire de...
THE NUMBER OF SPARSELY EDGED LABELLED HAMILTONIAN GRAPHS.unkown
THE NUMBER OF SPARSELY EDGED LABELLED HAMILTONIAN GRAPHS by E. M. WRIGHTt...}. (1) Here I give exact formulae for h(n, n + k) for k = 1,...
A clique-difference encoding scheme for labelled k-path graphs.unkown
encoding scheme for labelled k-path graphs P.R...number of labelled k-path graphs with n ...[1], Prüfer's article from 1918, a one-to-...
...regularization based on diffusion processes on graphs.unkown
graphs Arthur D Szlam Mathematics Department U.C...We show that these tasks can be tackled within... hier- Multiscale analysis of func- archical ...
更多相关标签:

All rights reserved Powered by 甜梦文库 9512.net

copyright ©right 2010-2021。
甜梦文库内容来自网络,如有侵犯请联系客服。zhit325@126.com|网站地图